104. 二叉树的最大深度

• 思路
  • example
  • 节点A深度：根节点到节点A的长度，根节点深度记为1。（自上而下，以根节点为基准往下看。）
    • 最大深度: 从根节点出发往下走能走到的最深位置的长度 （根节点到叶子节点的最长路径）
    • 最小深度: 从根节点出发往下走能走到的最浅位置的长度 （根节点到叶子节点的最短路径）
      • 叶子节点：左右子树都为空。
  • 节点A高度：以哪个叶子节点为基准？
  • 递归
    • 后序遍历（自下而上，后处理当前节点）：本质是求某种意义的高度。
      • 树的最大深度为3: max(节点9为根节点的子树的最大深度=1， 节点20为根节点的子树的最大深度=2) + 1
    • 前序遍历（自上而下，先处理当前节点）：直接求当前节点的深度，维护全局变量更新最大深度。需要“回溯”。
• 复杂度. 时间：O(n), 空间: O(n)

• 后序 （更好理解）自下而上 高度角度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def traversal(root): 
            if root == None:
                return 0
            leftDepth = traversal(root.left) # 以root.left为根节点的深度
            rightDepth = traversal(root.right) # 以root.right为根节点的深度
            return max(leftDepth, rightDepth) + 1 # 以root为根节点的深度
        return traversal(root)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

• 前序 自上而下，深度角度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root, depth):
            nonlocal res
            if root == None:
                return 
            res = max(res, depth) 
            dfs(root.left, depth + 1)
            dfs(root.right, depth + 1)
            return 
        res = 0
        dfs(root, 1)
        return res

• BFS: 层序遍历 (迭代)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        level = 0
        que = collections.deque([root])
        while que:
            size = len(que)
            level += 1
            for _ in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return level 

111. 二叉树的最小深度

image

• 思路
  • example
  • 递归，后序遍历。注意节点的左右子树为空才算叶子节点。
    • 最大深度：只要取左右子树的最大的深度即可。
    • 最小深度：
      • 左空右空，说明深度取决于当前节点（空与否）。
      • 左空右非空：取右子树最小深度。
      • 左非空右空：取左子树最小深度。
      • 左非空右非空：取左右最小深度 + 1 即可。
• 复杂度. 时间：O(n), 空间: O(n)

• 后序

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            if root == None:
                return 0
            if root.left == None and root.right == None:
                return 1
            left_min, right_min = float('inf'), float('inf')
            if root.left:
                left_min = traversal(root.left)
            if root.right: 
                right_min = traversal(root.right)
            return min(left_min, right_min) + 1 
        return traversal(root)  

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0 
        if root.left == None and root.right == None:
            return 1
        left, right = float('inf'), float('inf')
        if root.left:
            left = self.minDepth(root.left)
        if root.right:
            right = self.minDepth(root.right)
        return min(left, right) + 1

-- Common Mistake

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0 
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        return min(left, right) + 1

• 前序

code

• BFS: 层序遍历 (迭代)

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        res = 0
        que = collections.deque([root])
        while que:
            size = len(que)
            res += 1
            for _ in range(size):
                node = que.popleft()
                if node.left == None and node.right == None:
                    return res   
                if node.left: 
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

222. 完全二叉树的节点个数

• 思路
  • example
  • 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
  • 暴力法：递归后序遍历(自底向上)所有节点累计节点为个数即可。
    • 时间复杂度高，没有用到“完全二叉树”的性质。
• 复杂度. 时间：, 空间:

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            if root == None:
                return 0
            left_num = traversal(root.left)
            right_num = traversal(root.right)
            return left_num + right_num + 1
        return traversal(root)

• 优化：利用完全二叉树和满二叉树的性质。
  

• 满二叉树节点数： （根节点深度记为）
• 对当前节点，深度遍历一路向左得到“左遍历”最大深度，同理深度遍历一路向右得到“右遍历”最大深度。（自上而下）
  • 如果两个深度相同，说明当前节点所在的子树为满二叉树（基于完全二叉树的假设）。
  • 如果两个深度不相同，刚其中一个为满二叉树，另一个非满。不管怎样，递归调用函数计算得到两个子树的节点数，相加再加1即可。
• 时间：?
  • TBA

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        leftNode, rightNode = root.left, root.right
        leftDepth, rightDepth = 1, 1
        while leftNode: # 一路向左，左子树深度
            leftDepth += 1
            leftNode = leftNode.left 
        while rightNode: # 一路向右，右子树深度
            rightDepth += 1
            rightNode = rightNode.right 
        if leftDepth == rightDepth: # 满二叉树
            return 2**leftDepth - 1
        return self.countNodes(root.left) + self.countNodes(root.right) + 1 # 递归调用

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0 
        cur = root
        left_depth = 1
        while cur.left:
            left_depth += 1
            cur = cur.left 
        cur = root 
        right_depth = 1 
        while cur.right:
            right_depth += 1
            cur = cur.right 
        if left_depth == right_depth:
            return 2**left_depth - 1
        return self.countNodes(root.left) + self.countNodes(root.right) + 1  

114. Flatten Binary Tree to Linked List

• 思路
  • example
  • 遍历解决 (前序） - 需要额外空间

class Solution:
    def flatten(self, root: TreeNode) -> None:
        preorderList = list()

        def preorderTraversal(root: TreeNode):
            if root:
                preorderList.append(root)
                preorderTraversal(root.left)
                preorderTraversal(root.right)
        
        preorderTraversal(root)
        size = len(preorderList)
        for i in range(1, size):
            prev, curr = preorderList[i - 1], preorderList[i]
            prev.left = None
            prev.right = curr

• 分解子问题 （后序遍历）

  
  

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root == None:
            return 
        self.flatten(root.left)
        self.flatten(root.right)
        new_left = root.left 
        new_right = root.right 
        root.left = None 
        root.right = new_left
        cur = root # 避免讨论corner case (new_left是否为None)
        while cur.right:
            cur = cur.right 
        cur.right = new_right 

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root == None:
            return 
        self.flatten(root.left)
        self.flatten(root.right) 
        old_left = root.left 
        old_right = root.right 
        root.left = None 
        root.right = old_left 
        while root.right:
            root = root.right 
        root.right = old_right 

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root == None:
            return 
        self.flatten(root.left)
        self.flatten(root.right) 
        old_left, old_right = root.left, root.right 
        root.right = old_left 
        root.left = None 
        cur = root
        while cur.right:
            cur = cur.right 
        cur.right = old_right