Day 20 二叉樹：654. 最大, 617. 合并, 700. 搜索樹搜索, 98. 驗(yàn)證搜索樹

654. 最大二叉樹

  • 思路
    • example
    • 遞歸，前序遍歷
    • 空節(jié)點(diǎn)
      • 遞歸Base case包含空節(jié)點(diǎn)
      • 或 遞歸Base case不包含空節(jié)點(diǎn)：調(diào)用遞歸函數(shù)前需要加判斷語句 if root.left:
    • 傳遞數(shù)組范圍
  • 復(fù)雜度. 時(shí)間：O(n), 空間: O(n)
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def traversal(nums, left, right): # left closed, right closed
            if left > right:
                return None
            val_max, idx_max = -float('inf'), -1
            for i in range(left, right+1):
                if nums[i] > val_max:
                    val_max = nums[i]
                    idx_max = i  
            node = TreeNode(val_max)
            node.left = traversal(nums, left, idx_max - 1)
            node.right = traversal(nums, idx_max + 1, right)
            return node  
        return traversal(nums, 0, len(nums)-1) 

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        if n == 0:
            return None 
        max_ = -float('inf')
        idx = -1
        for i in range(n):
            if nums[i] > max_:
                max_ = nums[i]
                idx = i
        root = TreeNode(nums[idx])
        root.left = self.constructMaximumBinaryTree(nums[0:idx])
        root.right = self.constructMaximumBinaryTree(nums[idx+1:])
        return root

617. 合并二叉樹

  • 思路
    • example
    • 把tree2合并到tree1上 (不需要額外構(gòu)造樹)
      • if tree1 == None: return tree2 (could be None)
      • if tree2 == None: return tree1
      • 否則root1.val += root2.val
    • 遞歸，前序遍歷 （中序，后序亦可）
  • 復(fù)雜度. 時(shí)間：O(n), 空間: O(n)
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None:
            return root2 
        if root2 == None:
            return root1 
        root1.val += root2.val 
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right) 
        return root1 

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None:
            return root2 
        if root2 == None:
            return root1 
        root1.val += root2.val 
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right) 
        return root1
  • 迭代，層序，deque
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None: 
            return root2
        if root2 == None:
            return root1 
        que = collections.deque()
        que.append((root1, root2))
        while que:
            size = len(que)
            for _ in range(size):
                node1, node2 = que.popleft()
                node1.val += node2.val 
                if node1.left and node2.left: # 兩個(gè)左節(jié)點(diǎn)都非空時(shí)才入隊(duì)列
                    que.append((node1.left, node2.left))
                if node1.right and node2.right: # 兩個(gè)右節(jié)點(diǎn)都非空時(shí)才入隊(duì)列
                    que.append((node1.right, node2.right))
                if node1.left == None and node2.left:
                    node1.left = node2.left
                if node1.right == None and node2.right:
                    node1.right = node2.right 
                # 其它不需要處理
        return root1

700. 二叉搜索樹中的搜索

  • 思路
    • example
    • 給定二叉搜索樹（BST）的根節(jié)點(diǎn) root 和一個(gè)整數(shù)值 val。
      你需要在 BST 中找到節(jié)點(diǎn)值等于 val 的節(jié)點(diǎn)。 返回以該節(jié)點(diǎn)為根的子樹。 如果節(jié)點(diǎn)不存在，則返回 null 。
    • 遞歸
    • Base case：空節(jié)點(diǎn)或root.val == val
  • 復(fù)雜度. 時(shí)間：O(n), 空間: O(n)
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None:
            return None 
        if root.val == val:
            return root 
        elif root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)
  • 迭代 (二分）
    • 二叉搜索樹：有序。不需要利用?；蜿?duì)列的幫助就可以實(shí)現(xiàn)迭代遍歷。
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val == val:
                return root 
            elif root.val < val:
                root = root.right 
            else:
                root = root.left 
        return None

98. 驗(yàn)證二叉搜索樹

有效 二叉搜索樹定義如下：
- 節(jié)點(diǎn)的左子樹只包含 小于 當(dāng)前節(jié)點(diǎn)的數(shù)。
- 節(jié)點(diǎn)的右子樹只包含 大于 當(dāng)前節(jié)點(diǎn)的數(shù)。
- 所有左子樹和右子樹自身必須也是二叉搜索樹。

  • 思路
    • example
    • 遞歸
    • 注意搜索樹的定義
      • 驗(yàn)證左右子樹是否搜索樹
      • 只比較root.val，root.left.val, root.right.val是不夠的。下面的遞歸前序遍歷是錯(cuò)誤的。還需要驗(yàn)證根節(jié)點(diǎn)值小于右子樹最小值，大于左子樹最大值。
    • 上圖中，就算右子樹改為[6,3,7]也是False.
  • 復(fù)雜度. 時(shí)間：O(n), 空間: O(n)
# 錯(cuò)誤代碼
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            if root == None:
                return True
            if root.left and root.left.val >= root.val:
                return False
            if root.right and root.right.val <= root.val:
                return False
            return traversal(root.left) and traversal(root.right)
        return traversal(root)
  • 遞歸，中序遍歷。BST利用中序遍歷就是自然的遞增順序！
    • 中序遍歷中，如果知道當(dāng)前節(jié)點(diǎn)的pre節(jié)點(diǎn)，并且是遞增順序，那么符合要求。
    • 最簡單的方法，中序遍歷得到一個(gè)數(shù)組，再判斷該數(shù)組是不是嚴(yán)格遞增順序。
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            nonlocal pre
            if root == None:
                return True  
            flag_left = traversal(root.left)
            if flag_left == False:
                return False
            if pre and root.val <= pre.val:
                return False 
            pre = root 
            flag_right = traversal(root.right) 
            if flag_right == False:
                return False 
            return True 
        pre = None     
        return traversal(root)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root):
            nonlocal pre 
            if root == None:
                return True 
            if traversal(root.left) == False:
                return False 
            if pre and pre.val >= root.val:
                return False 
            pre = root 
            if traversal(root.right) == False:
                return False 
            return True 
        pre = None 
        return traversal(root)
  • 迭代，中序遍歷
    • cur + stack
    • 記錄pre 節(jié)點(diǎn)或者pre節(jié)點(diǎn)的數(shù)值。
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        cur = root  
        stack = []
        pre_val = -float('inf')
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left 
            else: 
                cur = stack.pop()
                if pre_val >= cur.val:
                    return False
                pre_val = cur.val  
                cur = cur.right 
        return True
  • 遞歸，前+后 序，遞歸函數(shù)參數(shù)
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root, min_val, max_val):
            if root == None:
                return True 
            if root.val >= max_val or root.val <= min_val:
                return False  
            valid1 = traversal(root.left, min_val, root.val)
            valid2 = traversal(root.right, root.val, max_val)
            return valid1 and valid2  
        return traversal(root, -float('inf'), float('inf'))
  • 后序
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traverse(root):
            if root == None:
                return True, float('inf'), -float('inf') # !!!
            if root.left == None and root.right == None:
                return True, root.val, root.val 
            valid_left, min_left, max_left = traverse(root.left)  
            if valid_left == False:
                return False, min_left, max_left  
            valid_right, min_right, max_right = traverse(root.right)  
            if valid_right == False:
                return False, min_right, max_right  
            if max_left < root.val < min_right:
                return True, min(min_left, min_right, root.val), max(max_left, max_right, root.val)  
            return False, min(min_left, min_right, root.val), max(max_left, max_right, root.val)  
        res, min_, max_ = traverse(root)  
        return res
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容