陈浪平的博客
0%

树的遍历

发表于 更新于 分类于 Disqus：
本文字数： 2k 阅读时长 ≈ 2 分钟

深度优先遍历

树的基本操作，肯定要熟练掌握的。以下的三种遍历，其实就是通过中间的树的值什么时候遍历来命名的。左子树永远优先右子树遍历。而且以下三种遍历都是属于深度优先遍历（Depth First Search)，但是一般都是用的先序遍历。

inorder输出

就是中序遍历：

  • 先遍历左边的
  • 然后遍历中间的
  • 最后遍历右边的子树

python实现：

1
2
3
4
5
def helper(self, root, res):
    if root:
        self.helper(root.left, res)
        res.append(root.val)
        self.helper(root.right, res)

java实现:

1
2
3
4
5
6
7
private void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

preorder输出

先序遍历：

  • 先遍历根
  • 再遍历左子树
  • 最后遍历右子树

python实现：

1
2
3
4
5
def helper(self, root, res):
        if root:
            res.append(root.val)
            self.helper(root.left, res)
            self.helper(root.right, res)

java实现：

1
2
3
4
5
6
7
private void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

postorder输出

后序遍历：

  • 先遍历左子树
  • 在遍历右子树
  • 最后遍历根

python实现

1
2
3
4
5
6
7
8
def helper(self, root, res):
    if not root:
        return
    if root.left:
        self.helper(root.left, res)
    if root.right:
        self.helper(root.right, res)
    res.append(root.val)

java实现：

1
2
3
4
5
6
7
8
9
10
11
12
private void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    if (root.left != null) {
        postOrder(root.left);
    }
    if (root.right != null) {
        postOrder(root.right);
    }
    System.out.print(root.val + " ");
}

使用栈实现先序遍历

当然可以使用数据结构来实现，省点空间，但是我感觉还是递归更容易阅读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void preOrderInStack(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode tmp = root;
    while (tmp != null || !stack.isEmpty()) {
        if (tmp != null) {
            System.out.print(tmp.val + "  ");
            stack.push(tmp);
            tmp = tmp.left;
        } else {
            // 左子树已经完毕
            tmp = stack.pop().right;
        }
    }
}

广度优先遍历

一般来说广度优先就只有一种遍历（因为左边的永远优先于右边的），利用队列很简单就实现了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void bfs() {
    Deque<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int length = queue.size();
        for (int i = 0; i < length; i++) {
            TreeNode tmp = queue.getFirst();
            queue.removeFirst();
            System.out.print(tmp.val + " ");
            if (tmp.left != null) {
                queue.add(tmp.left);
            }
            if (tmp.right != null) {
                queue.add(tmp.right);
            }
        }
    }
}