Binary Tree

Someone2022年4月27日
大约 13 分钟

本文主要研究了:

  • 二叉树的三种遍历方式:递归和迭代实现
  • 二叉树相关的例题解析

二叉树的前序遍历

递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(node):
            if not node:
                return
            res.append(node.val)
            preorder(node.left)
            preorder(node.right)

        res = list()
        preorder(root)
        return res

上述就是递归实现的而阐述的前序遍历。除此之外,还有一种不是很 Python 的但是较为通用、方便理解的方法:

class Solution:
    # 前序遍历函数
    def preOrder(self, root: TreeNode, res):
        if root == None:
            return
        res.append(root.val)
        self.preOrder(root.left, res)
        self.preOrder(root.right, res)

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.preOrder(root, res)
        return res

其本质上就是把递归的结果收集 res 增加到了递归中去了。

我们还有一种很 Python 的实现方式如下:

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

是不是很优雅?哈哈,值得深入去理解!

迭代法

前序遍历的迭代实现依赖于栈结构,具体而言不是很好理解的,需要多加理解才可以,其实现如下:

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        while stack or root:
            while root:
                res.append(root.val)
                stack.append(root.right)
                root = root.left
            root = stack.pop()

        return res

从上述代码中可以看出来的规律如下:

  1. stack 中自始至终只加入了 root.right
  2. root.left 都是被遍历完毕了

二叉树的中序遍历

递归法

二叉树的中序遍历递归解法参考如下:

def dfs(root: Optional[TreeNode], res):
    if not root:
        return
    dfs(root.left, res)
    res.append(root.val)
    dfs(root.right, res)

迭代法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        res = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res

这种方法理解起来并不是很直观,我们需要加深对“中序遍历:左 -- 根 -- 右” 的理解,就是说我们先遍历左子树,然后遍历完之后再走到右子树。

我们可以举例说:

上述二叉树的中序遍历结果是 [4, 2, 5, 1, 6, 3]

我们第一趟的时候,栈内元素是 [1, 2, 4], 然后 root 指向了 Null, 这时候我们给结果里面增加元素,到 root.right 不是 Null 了,再继续找。

同样的,我们可以根据中序遍历的应用题目 面试题 04.06. 后继者open in new window 来加深印象。

二叉树的层次遍历

LC102 - Binary Tree Level Order Traversalopen in new window

代码实现如下:

Code GitHub - binary_treeopen in new window

def levelOrder(root):
    '''
    二叉树的层次遍历
    '''
    if not root:
        return []

    result = [[root.data]]  # 存储层次遍历的结果
    current = [root]  # 存储当前层次内的节点,在循环里面更新

    while True:
        node_list = []  # 临时存储节点
        for node in current:  # 循环内遍历
            if node.left:
                node_list.append(node.left)
            if node.right:
                node_list.append(node.right)
        if node_list == []:
            break
        vals = [node.data for node in node_list]  # 拿出当前层次的节点的值
        result.append(vals)
        current = node_list  # 更新层次
    return result

这是目前可以写出的比较高效的一个算法,应当牢记。

也可以参考下面的解法:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = collections.deque([root])
        res = []
        while q:
            # 这个 node 已经取出了
            size = len(q)
            tmp = []
            for _ in range(size):
                # 在 for 循环中把 q 这个队列拿空
                # 第一次 for 迭代循环的是 root 节点
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                tmp.append(node.val)

            if tmp:
                res.append(tmp)

        return res

也可以使用递归的方法:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        res = []

        def dfs(root: TreeNode, res, level: int):
            if len(res) == level:
                res.append([])
            res[level].append(root.val)
            
            if root.left:
                dfs(root.left, res, level + 1)
            if root.right:
                dfs(root.right, res, level + 1)

        dfs(root, res, 0)

        return res

当遍历到一个新的深度 level,而最终结果 res 中还没有创建 level 对应的列表时,应该在 res 中新建一个列表用来保存该 level 的所有节点。

例题

LC606 根据二叉树创建字符串(前序遍历)

https://leetcode-cn.com/problems/construct-string-from-binary-tree/open in new window

题目的大概意思是,前序遍历二叉树,但是给每个子节点都用括号包裹起来,如果子节点是空的话,就不用括号。是一道简单题。

这道题目的核心难点在于,如何包裹。解法给出了一个讨论情况然后分别处理的方法:

  1. 左右节点都没有了,返回;
  2. 左节点有,右节点没有,左节点包裹后继续递归;
  3. 左节点没有,右节点有,左节点用空括号(题目要求),右节点递归
  4. 左右节点都有,都递归

其实现方式如下:

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ''
        
        res = str(root.val)
        if not root.left and not root.right:
            return res

        left = self.tree2str(root.left)
        right = self.tree2str(root.right)

        res += '(' + left + ')'
        if right:
            res += '(' + right + ')'

        return res

LC101 对称二叉树

101. 对称二叉树open in new window

给定二叉树,判断二叉树是否镜像对称。

    1
   / \
  2   2
 / \ / \
3  4 4  3

DFS 解法

这是该题目的 DFS(递归)解法。

代码如下:

class SolutionDFS:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 反例 [1]
        if not root.right and not root.left:
            return True

        # if not root.left or not root.right:
        #     return False

        def dfs(left, right):
            # 递归终止条件,两个节点都为空
            if not left and not right:
                return True

            if not left or not right:
                return False

            if left.val != right.val:
                return False

            return dfs(left.left, right.right) and dfs(left.right, right.left)

        return dfs(root.left, root.right)

从代码中我们可以看出,我们定义递归终止条件:

  1. 两个节点都为空,返回 True, 递归终止
  2. 两个节点中有一个不存在,不对称,返回 False
  3. 两个节点的值不相等,返回 False

在这些条件满足以后,我们对 left.leftright.right等分别递归即可求出结果。

BFS 解法

101. 对称二叉树open in new window

给定二叉树,判断二叉树是否镜像对称。

    1
   / \
  2   2
 / \ / \
3  4 4  3

可以看出,上述中就是一个对称的二叉树,我们得出一个简单的规律:

  1. 对于某个节点,如果其没有左节点或者右节点,那么其肯定不是一个对称二叉树;
  2. 对于某个节点,其兄弟节点的左右节点值要与自己的左右节点值对应相等。我们该如何保证这个呢?

其对应的代码如下:

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return False

        q = collections.deque([(root, root)])
        while q:
            left, right = q.popleft()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False

            q.append((left.left, right.right))
            q.append((left.right, right.left))

        return True

这种解法的思路在于,在队列中同时取出两个节点 left, right,然后判断其值是否相等,再将他们的孩子中按照 (left.left, right.right) 一组,(left.right, right.left)一组放入队列中。

还有一种解法是,往队列中放 4 次元素,按照 left.left, right.right, left.right, right.left 的顺序,然后逐一判断即可。

LC111 二叉树的最小深度

二叉树的最小深度open in new window

🏀🏀🏀 我们根据“概览”中的原则对这个问题进行分析:起点就是 root 节点,终点就是最靠近根节点的那个叶子节点(叶子节点的左右子节点都是 null)。

BFS 解法

其使用 BFS 的解法如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = collections.deque()
        first_node = (root, 1)
        queue.append(first_node)

        while queue:
            node, depth = queue.popleft()
            # 判断是否到达终点,终止条件
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))

        return 0

LC104 二叉树的最大深度

DFS 解法

104. 二叉树的最大深度open in new window

💓💓💓 思考 🧡🧡🧡

如何用 DFS 的思维来思考这个问题呢?

假设我们已经知道了左子树和右子树的最大深度 l, r, 那么整个二叉树的最大深度就是根节点的深度 1 加上左右子树中的最大深度,用公式表达是:

depth=max(l,r)+1 depth = max(l, r) + 1

所以我们可以使用深度有限搜索来计算二叉树的最大深度,具体而言就是递归计算出二叉树左子树和右子树的最大深度,然后再使用上述公式直接计算出二叉树的最大深度。

而二叉树左右子树的深度也都可以通过相同的方法递归获得,递归在访问到空节点时退出。

复杂度分析

该问题使用 DFS 求解,其时间复杂度为 O(n)O(n), 每个节点在递归中只被遍历一次。

其空间复杂度为 O(height)O(height),与二叉树的高度有关。由于递归需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。

问题求解

这个题目存在 DFS 和 BFS 解法,下面是这个题目的 DFS 解法:

  • 解法:使用辅助函数来进行递归:

    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
    
            def dfs(node: TreeNode):
                if not node:
                    return 0
    
                return max(dfs(node.right), dfs(node.left)) + 1
    
            return dfs(root)
    

    上述做法使用了一个 dfs()辅助函数进行递归,我们也可以不使用辅助函数。

  • 解法:直接递归:

    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            return max(self.maxDepth(root.right), self.maxDepth(root.left)) + 1
    

    这个不带辅助函数的解法是比带辅助函数的解法稍慢的,但是代码更加简洁。

BFS 解法

对比求二叉树的最小深度,其代码如下:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        q = collections.deque([(root, 1)])
        res = 1
        while q:
            node, depth = q.popleft()
            res = max(res, depth)
            if node.left:
                q.append((node.left, depth + 1))
            if node.right:
                q.append((node.right, depth + 1))
        return res

除此之外,该题目还存在 DFS 解法,可以参考上文。

LC102 二叉树的层序遍历

102. 二叉树的层序遍历open in new window

二叉树的层序遍历也会使用到 BFS 的思想,这个题目存在以下几个难点:

  1. 如何构造最终的结果,即类似于 [[3], [9,20], [15,7]] 这样的 List of List 的形式?
  2. 能否继续使用上面的解法模板来求解这个问题?模板是否具有普适性?

BFS 解法

接下来看第一版本的代码:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = collections.deque([root])
        res = []
        while q:
            size = len(q)
            tmp = []
            for _ in range(size):
                # 在 for 循环中把 q 这个队列拿空
                # 第一次 for 迭代循环的是 root 节点
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                tmp.append(node.val)

            if tmp:
                res.append(tmp)

可以看出:

  1. 在每次迭代中,我们都保证了把同一层的元素进行迭代;即队列中存储的元素永远是在同一层的元素,然后计算出这些元素的个数,用 for 循环逐一进行遍历。

    ❗❗❗ BFS 为什么要使用队列?

    在这里我理解了为什么 BFS 要使用队列这个数据结构,我们用 for 循环逐一进行遍历的时候,还没被遍历到的“上一层”元素都是在队列头部的,使用队列能保证这些上一层元素都被“踢”出去,而不影响本层新进来的元素。

  2. 这个题目的关键就是用 for 循环保证了同一层元素的遍历。

LC107 二叉树的层序遍历II

107. 二叉树的层序遍历 IIopen in new window

这个题目不同于二叉树层次遍历的地方在于,**给定一个二叉树,返回其节点值自底向上的层序遍历。 **

为了达到这个效果,我们可以在每次遍历之后,将结果放在结果集的头部,这样就可以得到我们想要的输出形式了。

其相对于上述代码的不同在于:

res = collections.deque()

# 向左端插入
res.appendleft(tmp)

# 返回时进行类型转换
return list(res)

当然也可以使用上面的代码直接将结果反转。

LC103 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历open in new window

这道题目是上面二叉树层序遍历的变种题目,题目的描述为:

给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

我们对题目进行分析可以发现遍历顺序和层级的关系:

层数遍历顺序
第一层(root)从左往右
第二层从右往左
第三次从左往右
第四层从右往左
奇数层从左往右
偶数层从右往左

我们发现遍历的顺序是和层级有关的,因此我们可以根据层级来确定遍历顺序:

🔴🔴🔴 遍历顺序,需要注意的是,我们一定要在队列中先添加左节点,再添加右节点,这个顺序需要保证,才能与后面的 depth % 2 == 0 配套。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        q = collections.deque([(root, 1)])
        res = []
        depth = 1
        while q:
            size = len(q)
            tmp = []
            for _ in range(size):
                node, depth = q.popleft()
                # 注意遍历顺序
                if node.left:
                    q.append((node.left, depth + 1))
                if node.right:
                    q.append((node.right, depth + 1))

                tmp.append(node.val)
                
            if depth % 2 == 0:
                # 偶数层从右往左
                tmp.reverse()
            if tmp:
                res.append(tmp)

        return res

LC543 二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/open in new window

class Solution:
    def __init__(self):
        self.res = 1

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def depth(node: TreeNode):
            if not node:
                return 0

            left = depth(node.left)
            right = depth(node.right)

            self.res = max(self.res, left + right + 1)
            return max(left, right) + 1
        depth(root)
        return self.res - 1

面试题 04.06. 后继者

面试题 04.06. 后继者open in new window

设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。

如果指定节点没有对应的“下一个”节点,则返回null

中序遍历

我们可以使用中序遍历的方法来求解这个问题,并且中序遍历过程中,维护上一个访问的节点。

中序遍历部分,可以直接套用迭代的中序遍历模板。

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        pre, cur = None, root

        stack = []

        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            if pre == p:
                return cur
            
            pre = cur
            cur = cur.right

        return None

在实现这个代码的时候,有几点我没有理解透彻,导致写错:

  1. pre, cur = None, root 初始值的赋值需要好好体会
  2. stack.append(cur) 这边是 cur 入栈,入栈以后再遍历左边
  3. cur = stack.pop() 出栈的步骤不要忘记

BST 特性解法

这道题目除了可以根据中序遍历来求解外,也可以根据 BST 的特点进行求解。

@todo

Loading...