找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法专栏】二叉树的几种遍历方式(原创)

admin 2019-4-11 19:21 106人围观 C++相关




本系列是《剑指offer》或leetcode的JavaScript版本。

每期1-2个算法,也有可能是一个类别。

文章包括题目、思路以及代码。

如果您对本期有不同或者更好的见解,请后台留言,喜欢请点个好看,谢谢阅读。

中序遍历


给定一个二叉树,返回它的 中序 遍历。

示例:

  1. 输入:[1,null,2,3]

  2. 1

  3. \

  4. 2

  5. /

  6. 3

  7. 输出:[1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

代码


递归实现

  1. var inorderTraversal =function(root, array =[]){

  2. if(root){

  3. inorderTraversal(root.left, array);

  4. array.push(root.val);

  5. inorderTraversal(root.right, array);

  6. }

  7. return array;

  8. };

非递归实现

  • 取跟节点为目标节点,开始遍历

  • 1.左孩子入栈 -> 直至左孩子为空的节点

  • 2.节点出栈 -> 访问该节点

  • 3.以右孩子为目标节点,再依次执行1、2、3

  1. var inorderTraversal =function(root){

  2. const result =[];

  3. const stack =[];

  4. let current = root;

  5. while(current || stack.length >0){

  6. while(current){

  7. stack.push(current);

  8. current = current.left;

  9. }

  10. current = stack.pop();

  11. result.push(current.val);

  12. current = current.right;

  13. }

  14. return result;

  15. };

前序遍历


给定一个二叉树,返回它的 前序 遍历。

示例:

  1. 输入:[1,null,2,3]

  2. 1

  3. \

  4. 2

  5. /

  6. 3

  7. 输出:[1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

代码


递归实现

  1. var preorderTraversal =function(root, array =[]){

  2. if(root){

  3. array.push(root.val);

  4. preorderTraversal(root.left, array);

  5. preorderTraversal(root.right, array);

  6. }

  7. return array;

  8. };

非递归实现

  • 取跟节点为目标节点,开始遍历

  • 1.访问目标节点

  • 2.左孩子入栈 -> 直至左孩子为空的节点

  • 3.节点出栈,以右孩子为目标节点,再依次执行1、2、3

  1. var preorderTraversal =function(root){

  2. const result =[];

  3. const stack =[];

  4. let current = root;

  5. while(current || stack.length >0){

  6. while(current){

  7. result.push(current.val);

  8. stack.push(current);

  9. current = current.left;

  10. }

  11. current = stack.pop();

  12. current = current.right;

  13. }

  14. return result;

  15. };

后序遍历


给定一个二叉树,返回它的 后序 遍历。

示例:

  1. 输入:[1,null,2,3]

  2. 1

  3. \

  4. 2

  5. /

  6. 3

  7. 输出:[3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

代码


递归实现

  1. var postorderTraversal =function(root, array =[]){

  2. if(root){

  3. postorderTraversal(root.left, array);

  4. postorderTraversal(root.right, array);

  5. array.push(root.val);

  6. }

  7. return array;

  8. };

非递归实现

  • 取跟节点为目标节点,开始遍历

  • 1.左孩子入栈 -> 直至左孩子为空的节点

  • 2.栈顶节点的右节点为空或右节点被访问过 -> 节点出栈并访问他,将节点标记为已访问

  • 3.栈顶节点的右节点不为空且未被访问,以右孩子为目标节点,再依次执行1、2、3

  1. var postorderTraversal =function(root){

  2. const result =[];

  3. const stack =[];

  4. let last =null;// 标记上一个访问的节点

  5. let current = root;

  6. while(current || stack.length >0){

  7. while(current){

  8. stack.push(current);

  9. current = current.left;

  10. }

  11. current = stack[stack.length -1];

  12. if(!current.right || current.right == last){

  13. current = stack.pop();

  14. result.push(current.val);

  15. last = current;

  16. current =null;// 继续弹栈

  17. }else{

  18. current = current.right;

  19. }

  20. }

  21. return result;

  22. }




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:code秘密花园,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......


关于进行手机实名认证的紧急通知!
按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了