总结一下二叉树的三种遍历方式,分别为前序遍历、中序遍历、后序遍历，每种遍历方式用两种方法:递归遍历和迭代遍历

 

1.首先来分析一下二叉树的前序遍历

　　前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

　　如图所示：

　　

　　　递归方法如下：

  1. 1 public List<Integer> preorderTraversal(TreeNode root) {
  2. 2        List<Integer> list=new ArrayList();
  3. 3         if(root!=null){
  4. 4             list.add(root.val);
  5. 5             list.addAll(preorderTraversal(root.left));
  6. 6             list.addAll(preorderTraversal(root.right));
  7. 7         }
  8. 8         return list;
  9. 9     }

　　　代码分析：先往集合中插入根节点的值，然后到根的左叶子节点，直到左叶子节点为null,右子节点相同原理，即可前序遍历出二叉树；  

 

　　　迭代方法如下：

　　　

  1.  1 List<Integer> list=new ArrayList();
  2.  2         if(root==null){
  3.  3             return list;
  4.  4         }
  5.  5        Stack<TreeNode> stack= new Stack();
  6.  6         stack.push(root);
  7.  7         while(stack.size()>0){
  8.  8             TreeNode treeNode=stack.pop();
  9.  9             list.add(treeNode.val);
  10. 10             if(treeNode.right!=null){
  11. 11                 stack.push(treeNode.right);
  12. 12             }
  13. 13             if(treeNode.left!=null){
  14. 14                 stack.push(treeNode.left);
  15. 15             }
  16. 16         }
  17. 17         return list;

　　　代码分析: 用迭代方法遍历二叉树， 我们需要用到栈来保存节点，通过栈先进后出的特性，我们先把根节点存入栈中，然后步骤如下

　　　　　　（1）当栈中元素数量大于0时

　　　　　　（2）取出最上面的栈元素，将其值放入集合中，查看是否有右叶子节点，有的话放入栈中，查看是否有左叶子节点，有的话放入栈中。

　　　　　　（3）当栈中所有元素均被取出，结束迭代循环，返回集合。

2.二叉树的中序遍历

　　中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

　　

　　递归方法如下：

　　　　

  1. 1 List<Integer> list=new ArrayList();
  2. 2         if(root!=null){
  3. 3             list.addAll(inorderTraversal(root.left));
  4. 4             list.add(root.val);
  5. 5             list.addAll(inorderTraversal(root.right));
  6. 6         }
  7. 7         return list;

　　

　　迭代方法如下：

　　

  1.  1 List<Integer> list=new ArrayList();
  2.  2        Stack<TreeNode> stack= new Stack();
  3.  3        while(true){
  4.  4            if(root!=null){
  5.  5                stack.push(root);
  6.  6                root=root.left;
  7.  7            }else{
  8.  8                if(stack.isEmpty()){
  9.  9                    return list;
  10. 10                }
  11. 11                TreeNode treeNode =stack.pop();
  12. 12                list.add(treeNode.val);
  13. 13                root=treeNode.right;
  14. 14            }
  15. 15        }

　　

　　　代码分析:

　　　　　　1.先将左子树全部压入栈中，然后取出左子树的最后一个节点

　　　　　　2.将弹出的节点的值存入数组中，判断是否有右子树节点，压入栈中，重复1步骤

　　　　　　3.直到弹出所有栈中节点，返回数组

　　3.二叉树的后序遍历

　　　　后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

　　　　

　　　　递归遍历:

  1. 1 List<Integer> list=new ArrayList();
  2. 2          if(root!=null){
  3. 3              list.addAll(inorderTraversal(root.left));
  4. 4              list.addAll(inorderTraversal(root.right)); 
  5. 5             list.add(root.val);
  6. 6         }
  7. 7          return list;

　　　　迭代方法如下：

  1. List<Integer> list=new ArrayList<Integer> ();
  2.         if(root==null){
  3.             return list;
  4.         }
  5.         Stack<TreeNode> stack =new Stack<TreeNode>();
  6.         stack.push(root);
  7.         while(!stack.isEmpty()){
  8.             TreeNode r=stack.pop();
  9.             list.add(0,r.val);
  10.             if(r.left!=null){
  11.                 stack.push(r.left);
  12.                 
  13.             }
  14.             if(r.right!=null){
  15.                 stack.push(r.right);
  16.             }
  17.         }
  18.         return list;

　　　　代码分析：

　　　　　二叉树后序的迭代遍历方法和二叉树前序的迭代遍历类似，

　　　　　通过遍历根右左的顺序 将值插入到list的头部位置，相当于进行了 reverse  返回的list变成了左右根 的顺序

　　　　

　　

版权声明：本文为pszp原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/pszp/p/9838088.html