理解二叉树的遍历-算法通关村

理解二叉树的遍历-算法通关村

1深入理解前中后序遍历

• 深度优先遍历有前中后三种情况，我们再从二又树的角度看递归，每次遇到递归，都按照上一篇的四步来写，可以更好地写出正确的递归算法。通过二叉树可以非常方便的理解递归，递归只处理当前这一层和下一层之间的关系，并不关心下层和下下层之间的关系，这就像老子只管养好儿子，至于孙子怎么样，那是儿子的事，你也不能瞎掺合。具体来说，我们总结了四条行之有效的方法来分解递归：
  •第一步：从小到大，或从大到小找递推
  •第二步：分情况讨论，明确结束条件
  • 第三步：组合出完整方法
  •第四步：想验证，则从大到小画图推演
  我们接下来就一步步看怎么做：

• 第一步：从小到大递推，分情况讨论

• 以这个二叉树为例：

• 

• 先选一个最小的子树：

• 

• 假如20为 head，则此时前序访问顺序是：

•   void visit1(Tree root){
        list.add(root);//20被访问
        list.add(root.left);//继续访问15
        list.add(root.right);//继续访问7
    }
  

• 然后再向上访问，看node(3)的情况

•   void visit2(){
        list.add(root);//3被访问
        root.left;//继续访问9
        root.right;//继续访问20
    }
  

• 这里的20是一个子树的父节点，访问方式与上面的visit1()一样，则合并到一起就是：

•   void visit(Tree root){
        list.add(root);
        visit(root.left);
        visit(root.right);
    }
  

• 这就是自下而上的递推。

• 第二步：分情况讨论，明确结束条件
  上面有了递归的主体，但是这个递归什么时候结束呢？很明显应该是root=nulI的时候。一般来说链表和二又树问题的终止条件都包含当前访问的元素为null。有些题目结束条件比较复杂，此时最好的方式就是先将所有可能的结束情况列举出来，然后整理一下就行了。

• 第三步：组合出完整方法
  到此为止，我们就能将完整代码写出来了，同时为了方便区分，我们将方法名换成preorder：

• 前序遍历（中左右）

•   public void preOrder(TreeNode root, List<Integer> res){
            if(root == null){
                return;
            }
            res.add(root.val);
            preOrder(root.left, res);
            preOrder(root.right, res);
        }
  

• 第四步 从大到小 画图推演写完之后对不对呢？递归的方法是很难调试的，即使对的，你也可能晕，这里介绍一种简单有效的验证方法—调用过程图法。我们可以画个过程图看一下，因为是两个递归函数，如果比较复杂，我们可以少画几组。
  递归的特征是“不撞南墻不回头”，一定是在执行到某个root=null了才开始返回，下图中的序号就是递归的完整过程：

• 

• 从图中可以看到，当root的一个子树为null的时候还是会执行递归，进入之后发现root==null了，然后就开始返回。这里我们要特别注意res.add（）的时机对不对，将其进入顺序依次写出来就是需要的结果。该过程明确之后再debug就容易很多，刚开始学习递归建议多画几次，熟悉之后就不必再画了。

• 中序遍历（左中右）

•   public void inOrder(TreeNode root){
            if(root == null){
                return;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
  

• 后序遍历（左右中）

•   public void postOrder(TreeNode root){
            if(root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
  

• 另外需要注意一点，面试，以及LeetCode里提供的方法可能不能直接用来递归，需要我们再创建一个方法.

• LeetCode144 二叉树前序遍历问题，此时给的函数 preorderTraversal() 就难以直接递归，我们可以自己再创建一个：

•   public class Solution_ {
        public List<Integer> preOrderTraversal(TreeNode root){
            List<Integer> res = new ArrayList<>();
            preOrder(root, res);
            return res;
        }
        
        public void preOrder(TreeNode root, List<Integer> res){
            if(root == null){
                return;
            }
            res.add(root.val);
            preOrder(root.left, res);
            preOrder(root.right, res);
        }
    }