数据结构全解析之二叉树的四大遍历方法

树遍历是对树中的每个节点只访问一次的过程。我们一提到树这一数据结构，很多人首先想到的就是树的遍历。这是因为，不管是在老师讲述树这一数据结构时，还是在面试时，亦或是在实际应用中，二叉树的遍历都是反复会出现的。

我们常说二叉树这种数据结构是优雅的，抛开实用方面不谈，多种多样二叉树的遍历方法完美的展现了这一点。不同的遍历方法把树的节点展开成列表的方式，而每种遍历方法都能从树中更加直观的提取出来一些信息。通过学习不同的树的遍历方法，我们能对二叉树有一个更加深入的理解。

1. 前序遍历

前序遍历是指先访问根，然后访问子树的遍历方式。如果二叉树为空，则遍历结果为空，否则先访问根节点，然后前序遍历左子树，然后前序遍历右子树。如下图所示：

image

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

上述用递归方法来解决前序遍历，同样，我们可以用栈这种数据结构来代替递归函数的函数栈，实现同样的功能。主要思想就是先将根节点压入栈，然后根节点出栈并访问根节点，而后依次将根节点的右孩子、左孩子入栈，直到栈为空为止。

    public List < Integer > Preorder(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        stack.push(root);
        while (curr != null || !stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if(curr!=null){
                res.add(curr.val);
                stack.push(curr.right);
                stack.push(curr.left);
            }     
        }
        return res;
    }

2. 中序遍历

image

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

中序遍历的非递归方法的实现和前序遍历的非递归实现类似，只不过是将根节点开始直到最左叶子节点这条路径上所有的节点压入栈，然后最左叶子节点出栈并访问它，而后，用同样的方法去处理该叶子节点的右子树，直到栈为空为止。

 public List < Integer > inorder(TreeNode root) {
     List < Integer > res = new ArrayList < > ();
     Stack < TreeNode > stack = new Stack < > ();
     TreeNode curr = root;
     while (curr != null || !stack.isEmpty()) {
         while (curr != null) {
             stack.push(curr);
             curr = curr.left;
         }
         curr = stack.pop();
         res.add(curr.val);
         curr = curr.right;
     }
     return res;
}

3. 后序遍历