二叉树的遍历

递归法

递归的写法比较简单，三种遍历方式在写法上的不同仅仅是将便利的顺序根据要求调整即可，代码结构相同

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    preorder(root, result);
    return result;
}

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

中序遍历

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

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

后序遍历

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

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

迭代法

前序遍历

前序遍历是中左右，因此先根入栈、出栈，再将其右孩子、左孩子入栈，再出左孩子，将其右孩子、左孩子入栈，循环重复即可达到前序遍历的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    if (root == null) {
        return result;
    }
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        result.add(tmp.val);
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
    }
    return result;
}

中序遍历

循环进栈访问到最左下的节点至null，此时切换访问节点cur为stack.pop的节点，即为null的上一个节点（最左下的节点，此时栈已经pop该节点，栈的peek节点为最左下节点的父节点），res.add(cur)。cur=cur.right。

如果cur为空，则继续改变访问节点cur=pop进行循环，否则就继续从cur向左下方遍历至null，循环

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<Integer>();
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            result.add(cur.val);
            cur = cur.right;
        }
    }
    return result;
}

后序遍历

由于前序遍历是中左右，后序遍历是左右中，因此只需先把前序遍历修改为中右左，在将得出的中右左结果进行翻转记得到左右中的结果，即为后续遍历结果。

前序遍历Reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    if (root == null){
        return result;
    }
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        result.add(tmp.val);
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
    }
    Collections.reverse(result);
    return result;
}

正常的迭代前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    if (root == null){
        return result;
    }
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode prev = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (root.right == null || root.right == prev) {
            result.add(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
    return result;
}

迭代统一写法

注意队列使用Deque时应使用LinkedList而不是ArrayDeque，因为ArrayDeque不可以push(null)而LinkedList可以push(null)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            //从下面开始，不同的遍历按照倒序换位置即可
//-----------------------------------------------------------------
            //处理右节点
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            
            //处理中间结点
            stack.push(tmp);
            stack.push(null);
            
            //处理左节点
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
//-----------------------------------------------------------------
        } else {
            tmp = stack.pop();
            result.add(tmp.val);
        }
    }
    return result;
}

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
            stack.push(tmp);
            stack.push(null);
        } else {
            tmp = stack.pop();
            result.add(tmp.val);
        }
    }
    return result;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            stack.push(tmp);
            stack.push(null);
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        } else {
            tmp = stack.pop();
            result.add(tmp.val);
        }
    }
    return result;
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root != null){
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            stack.push(tmp);
            stack.push(null);
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        } else {
            tmp = stack.pop();
            result.add(tmp.val);
        }
    }
    return result;
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> res = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode tmp = queue.remove();
            res.add(tmp.val);

            if (tmp.left != null) {
                queue.add(tmp.left);
            }
            if (tmp.right != null) {
                queue.add(tmp.right);
            }
        }
        result.add(res);
    }
    return result;
}

三种非递归前序遍历写法

一直往左走,到头再处理右孩子(常规)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                result.add(root.val);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return result;
    }
}

先右孩子入栈再左孩子入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        if (root == null) {
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            result.add(tmp.val);
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        }
        return result;
    }
}

统一模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
            stack.push(tmp);
            stack.push(null);
        } else {
            tmp = stack.pop();
            result.add(tmp.val);
        }
    }
    return result;
}