Xing's Techlog

二叉树遍历算法总结

Posted on Edited on In

二叉树深度优先遍历和宽度优先遍历算法总结。

二叉树深度优先遍历算法

二叉树的中序遍历:

递归实现
1
2
3
4
5
6
7
public void inorderWalk(TreeNode root) {
    if (root != null) {
        inorderWalk(root.left);
        System.out.print(root.val);
        inorderWalk(root.right);
    }
}
迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void iterativeInorderWalk(TreeNode root) {
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while (p != null || !stack.isEmpty()) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        if (!stack.isEmpty()) {
            p = stack.pop();
            System.out.print(p.val);
            p = p.right;
        }
    }
}

二叉树的前序遍历:

递归实现
1
2
3
4
5
6
7
public void preorderWalk(TreeNode root) {
    if (root != null) {
        System.out.print(root.val);
        preorderWalk(root.left);
        preorderWalk(root.right);
    }
}
迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void iterativePreorderWalk(TreeNode root) {
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while (p != null || !stack.isEmpty()) {
        while (p != null) {
            System.out.print(p.val);
            stack.push(p);
            p = p.left;
        }
        if (!stack.isEmpty()) {
            p = stack.pop();
            p = p.right;
        }
    }
}

注意到前序遍历和中序遍历的迭代算法结构完全相同，只有处理当前节点语句的位置不同。

二叉树的后序遍历:

递归实现
1
2
3
4
5
6
7
public void postorderWalk(TreeNode root) {
    if (root != null) {
        postorderWalk(root.left);
        postorderWalk(root.right);
        System.out.print(root.val);
    }
}
迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void iterativePostorderWalk(TreeNode root) {
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    ArrayDeque<TreeNode> resStack = new ArrayDeque<>();
    TreeNode p = root;
    while (p != null || !stack.isEmpty()) {
        while (p != null) {
            resStack.push(p);
            stack.push(p);
            p = p.right;
        }
        if (!stack.isEmpty()) {
            p = stack.pop().left;
        }
    }
    while (!resStack.isEmpty()) {
        System.out.print(resStack.pop().val);
    }
}

二叉树的宽度优先遍历算法

层次遍历二叉树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void levelOrderWalk(TreeNode root) {
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode p = queue.poll();
        System.out.print(p.val);
        if (p.left != null) {
            queue.offer(p.left);
        }
        if (p.right != null) {
            queue.offer(p.right);
        }
    }
}

之字型遍历二叉树:

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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    Stack<TreeNode> rightStack = new Stack<>();
    Stack<TreeNode> leftStack = new Stack<>();
    rightStack.push(root);
    while (!rightStack.isEmpty() || !leftStack.isEmpty()) {
        TreeNode p;
        List<Integer> list = new ArrayList<>();
        while (!rightStack.isEmpty()) {
            p = rightStack.pop();
            list.add(p.val);
            if (p.left != null) leftStack.push(p.left);
            if (p.right != null) leftStack.push(p.right);
        }
        if (!list.isEmpty()) {
            res.add(list);
            list = new ArrayList<>();
        }
        while (!leftStack.isEmpty()) {
            p = leftStack.pop();
            list.add(p.val);
            if (p.right != null) rightStack.push(p.right);
            if (p.left != null) rightStack.push(p.left);
        }
        if (!list.isEmpty()) res.add(list);
    }
    return res;
}

从底向上层次遍历二叉树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    if (root == null) return new ArrayList<>();
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    List<List<Integer>> ans = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode pNode = queue.poll();
            if (pNode.left != null) queue.offer(pNode.left);
            if (pNode.right != null) queue.offer(pNode.right);
            level.add(pNode.val);
        }
        ans.add(0, level);
    }
    return ans;
}
Related Posts