TreeTraversalTemplate

发表于：
字数： 1355 阅读：≈ 3分钟
总结摘要
树遍历模板

Concept

DFS ~ Recursive

BFS ~ Iterative

遍历方式

  • 深度优先遍历(DFS)
    • 前序遍历(Pre-Order Traversal)
    • 中序遍历(In-Order Traversal)
    • 后序遍历(Post-Order Traversal)
  • 广度优先遍历(BFS)
    • 层次遍历(Level-Order Traversal)
    • 结果唯一

代码书写方式

  • Recursion
    • Levelorder
    • Preorder
    • Inorder
    • Postorder
  • Iteration
    • Levelorder
    • Preorder
    • Inorder
    • Postorder

RecursionTraversalTemplate

递归遍历模板

 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
33
34
35
36
37
38
39
40
41

public class RecursionTraversalTemplate {
    // 递归遍历实现深度优先遍历
    public void dfsRecursiveTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        dfsRecursiveTraversal(root.left);
        dfsRecursiveTraversal(root.right);
    }

    // 递归遍历实现深度优先查找
    public boolean dfsRecursiveSearch(TreeNode root, int value) {
        if (root == null) {
            return false;
        }
        if (root.val == value) {
            return true;
        }
        boolean left = dfsRecursiveSearch(root.left, value);
        boolean right = dfsRecursiveSearch(root.right, value);
        return left && right;
    }

    // 递归遍历实现深度优先层次查询
    public List<List<Integer>> dfsToLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        dfsToLevelOrder(root, 0, res);
        return res;
    }
    private void dfsToLevelOrder(TreeNode root, int depth, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        if (res.size() == depth) {
            res.add(new LinkedList<>());
        }
        res.get(depth).add(root.val);
        dfsToLevelOrder(root.left, depth+1, res);
        dfsToLevelOrder(root.right, depth+1, res);
    }
}

IterationTraversalTemplate

IterationTraversalTemplate

迭代遍历模板

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class IterationTraversalTemplate {
    // 迭代遍历实现广度优先查找，队列实现
    public TreeNode bfsIterationTraversalSearchByQueue(TreeNode root, int val) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                continue;
            }
            if (node.val == val) {
                return node;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }

        return null;
    }

    // 迭代遍历实现深度优先查找，栈实现
    public void dfsIterationTraversalByStack(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                continue;
            }
            if (node.left == null && node.right == null) {
                list.add(node.val);
            }
            stack.push(node.right);
            stack.push(node.left);
        }
    }
}

IterationTraversalLevelOrderTemplate 

 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

public class IterationTraversalLevelOrderTemplate {

   // 迭代遍历实现广度优先层次查询
    // calcMaxDepth 计算深度（层次）
    public int bfsIterationTraversalLevelOrder(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int depth = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

IterationTraversalInorderTemplate

迭代遍历实现中序遍历

 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 class IterationTraversalInorderTemplate {
    // bfs inorder binary tree
    public List<TreeNode> bfsInorderBT(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();

        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            res.add(node);
            cur = node.right;
        }

        return res;
    }
}

IterationTraversalPreorderTemplate

迭代遍历实现前序遍历

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class IterationTraversalPreorderTemplate {
    // bfs preorder binary tree
    public List<Integer> bfsPreorderBT(TreeNode root) {
        List<Integer> list = new LinkedList<>();

        if (root == null) {
            return list;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
    }


    // bfs preorder n-ary tree
    public List<Integer> bfsPreorderNAryTree(Node root) {
        List<Integer> list = new LinkedList<>();

        if (root == null) {
            return list;
        }

        Deque<Node> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            list.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
        }
        return list;
    }
}

IterationTraversalPostorderTemplate

迭代遍历实现后序遍历

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

public class IterationTraversalPostorderTemplate {
    // bfs postorder binary tree
    public void bfsPostorderBT(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            // 后序遍历顺序：左子树 --> 右子树 --> 中子树
            // 场景1：`cur.right == null`，右子树为空（从左子树或右子树返回），栈弹出中节点进行处理。
            // 场景2：`cur.right == pre`，右子树不为空，且从右子树返回，栈弹出中节点进行处理。
            //       节点 pre 指向最近处理的节点，`cur.right == pre`表示右子树已处理。
            // 场景3：`else`，右子树不为空，且从左子树返回，优先处理右子树。
            if (cur.right == null || cur.right == pre) {
                stack.pop();
                pre = cur;
                cur = null;
            } else {
                cur = cur.right;
            }
        }
    }

    // bfs postorder binary tree
    public List<Integer> bfsPostorderBT2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        LinkedList<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            res.addFirst(node.val);
        }

        return res;
    }


    // bfs postorder n-ary tree
    public List<Integer> bfsPostorderNAryTree(Node root) {
        if (root == null) {
            return Collections.emptyList();
        }

        LinkedList<Integer> res = new LinkedList<>();
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            node.children.forEach(stack::push);
            res.addFirst(node.val);
        }

        return res;
    }
}

END