104. 二叉樹的最大深度

• 思路
  • example
  • 節(jié)點(diǎn)A深度：根節(jié)點(diǎn)到節(jié)點(diǎn)A的長度，根節(jié)點(diǎn)深度記為1。（自上而下，以根節(jié)點(diǎn)為基準(zhǔn)往下看。）
    • 最大深度: 從根節(jié)點(diǎn)出發(fā)往下走能走到的最深位置的長度 （根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑）
    • 最小深度: 從根節(jié)點(diǎn)出發(fā)往下走能走到的最淺位置的長度 （根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最短路徑）
      • 葉子節(jié)點(diǎn)：左右子樹都為空。
  • 節(jié)點(diǎn)A高度：以哪個葉子節(jié)點(diǎn)為基準(zhǔn)？
  • 遞歸
    • 后序遍歷（自下而上，后處理當(dāng)前節(jié)點(diǎn)）：本質(zhì)是求某種意義的高度。
      • 樹的最大深度為3: max(節(jié)點(diǎn)9為根節(jié)點(diǎn)的子樹的最大深度=1， 節(jié)點(diǎn)20為根節(jié)點(diǎn)的子樹的最大深度=2) + 1
    • 前序遍歷（自上而下，先處理當(dāng)前節(jié)點(diǎn)）：直接求當(dāng)前節(jié)點(diǎn)的深度，維護(hù)全局變量更新最大深度。需要“回溯”。
• 復(fù)雜度. 時間：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為根節(jié)點(diǎn)的深度
            rightDepth = traversal(root.right) # 以root.right為根節(jié)點(diǎn)的深度
            return max(leftDepth, rightDepth) + 1 # 以root為根節(jié)點(diǎn)的深度
        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
  • 遞歸，后序遍歷。注意節(jié)點(diǎn)的左右子樹為空才算葉子節(jié)點(diǎn)。
    • 最大深度：只要取左右子樹的最大的深度即可。
    • 最小深度：
      • 左空右空，說明深度取決于當(dāng)前節(jié)點(diǎn)（空與否）。
      • 左空右非空：取右子樹最小深度。
      • 左非空右空：取左子樹最小深度。
      • 左非空右非空：取左右最小深度 + 1 即可。
• 復(fù)雜度. 時間：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. 完全二叉樹的節(jié)點(diǎn)個數(shù)

• 思路
  • example
  • 在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。
  • 暴力法：遞歸后序遍歷(自底向上)所有節(jié)點(diǎn)累計節(jié)點(diǎn)為個數(shù)即可。
    • 時間復(fù)雜度高，沒有用到“完全二叉樹”的性質(zhì)。
• 復(fù)雜度. 時間：, 空間:

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)

• 優(yōu)化：利用完全二叉樹和滿二叉樹的性質(zhì)。
  

• 滿二叉樹節(jié)點(diǎn)數(shù)： （根節(jié)點(diǎn)深度記為）
• 對當(dāng)前節(jié)點(diǎn)，深度遍歷一路向左得到“左遍歷”最大深度，同理深度遍歷一路向右得到“右遍歷”最大深度。（自上而下）
  • 如果兩個深度相同，說明當(dāng)前節(jié)點(diǎn)所在的子樹為滿二叉樹（基于完全二叉樹的假設(shè)）。
  • 如果兩個深度不相同，剛其中一個為滿二叉樹，另一個非滿。不管怎樣，遞歸調(diào)用函數(shù)計算得到兩個子樹的節(jié)點(diǎn)數(shù)，相加再加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 # 遞歸調(diào)用

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