Leetcode日记：94&144&145.前序、中序、后序遍历二叉树（递归与非递归）

问题介绍

这个不用多说，就是对二叉树的遍历，只用前序遍历举个例子。

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

基本就是按照遍历顺序打印结点。

递归解决方案

递归前序

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

递归中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    // method 1: recursion

    helper(root, res);
    return res;

    //helper function for method 1
    private void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
           }
       }
   }

递归后序

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> postorderTraversal1(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    dfs(root, ret);
    return ret;
}

private void dfs(TreeNode root, List<Integer> ret) {
    if (root != null) {
        dfs(root.left, ret);
        dfs(root.right, ret);
        ret.add(root.val);
    }
}

递归总结

其实就是打印语句或者说要求的操作摆放位置：

  • 前序：先执行操作，再访问左，再访问右
  • 中序：先访问左，再执行操作，再访问右
  • 后序：先访问左，再访问右，最后执行操作

非递归（利用栈）

非递归前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;
        }
    }
    return result;
}

非递归中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;
        }
    }
    return result;
}

我们用中序遍历来做个图示：首先我们假定给定的树如下

二叉树遍历
二叉树遍历

随后，代码用到了栈的数据结构，利用栈的性质来按顺序压栈出栈每一个结点。
栈
栈

结果
结果

可以看出，主要思路是只要节点不为空，就压栈，当节点为空时，弹出当前栈顶端元素，然后访问其右节点。
顺序的改变在于操作位于压栈还是弹栈，前序遍历是先进行操作（打印），再访问左元素。

非递归后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

这里的后序遍历利用了一个很巧妙的转换，把它看作一个对于右子树的先序遍历，然后反转result。
具体实现方式即，优先访问右节点p = p.right，访问到的每个不为空的节点压入栈，当访问节点为空时，弹出栈的顶端元素。再访问其左节点。

总结

树的遍历问题是非常基础的问题，这个要牢记，无论是递归还是非递归，之后做其他类的题目会很有帮助。