110. 平衡二叉樹

平衡二叉樹：一個二叉樹每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 。

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # # 1.遞歸 自頂向下 104ms
        # def depth(root):
        #     if not root:
        #         return 0
        #     return max(depth(root.left), depth(root.right))+1
        # if not root:
        #     return True
        # return abs(depth(root.left)-depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

        # 2.遞歸 自底向上
        self.res = True

        def helper(root):
            if not root:
                return 0
            left = helper(root.left)+1
            right = helper(root.right)+1
            if abs(left-right) > 1:
                self.res = False
            return max(left, right)
        helper(root)
        return self.res

101.對稱二叉樹

每一個節(jié)點的左右子樹相同


class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # # 1.遞歸
        # def twoTreeIsSymmetric(r1, r2):
        #     if not r1 and not r2:
        #         return True
        #     if not r1 or not r2:
        #         return False
        #     if r1.val != r2.val:
        #         return False
        #     return twoTreeIsSymmetric(r1.left, r2.right) and twoTreeIsSymmetric(r1.right, r2.left)

        # if not root:
        #     return True
        # return twoTreeIsSymmetric(root.left, root.right)

        # 2.BFS 利用隊列迭代 40ms 
        if not root:
            return True
        if not root.left and not root.right:
            return True
        if not root.left or not root.right:
            return False
        q = [(root.left, root.right)]
        while q:
            node1, node2 = q.pop(0)
            if node1.val != node2.val:
                return False
            if node1.left and node2.right:
                q.append((node1.left, node2.right))
            elif node1.left or node2.right:  # 有一個不存在
                return False

            if node1.right and node2.left:
                q.append((node1.right, node2.left))
            elif node1.right or node2.left:
                return False

        return True

102.二叉樹的層次遍歷（BST）

#2.利用一個隊列
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = [root]
        while q:
            n = len(q)
            layer = []
            for _ in range(n):
                node = q.pop(0)
                layer.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(layer)
        return res

104. 二叉樹的最大深度

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

        # # 2.迭代 dfs stack中加入層高
        # if not root:
        #     return 0
        # stack = [(1, root)]
        # lev = 0
        # while stack:
        #     height, cur = stack.pop(-1)
        #     lev = max(lev, height)
        #     if cur.left:
        #         stack.append((height+1, cur.left))
        #     if cur.right:
        #         stack.append((height+1, cur.right))
        # return lev

        # # 3.bfs記錄層高模板
        # if not root:
        #     return 0
        # queue = [root]
        # lev = 0
        # while queue:
        #     size=len(queue)
        #     for _ in range(size):
        #         cur=queue.pop(0)
        #         if cur.left:
        #             queue.append(cur.left)
        #         if cur.right:
        #             queue.append(cur.right)
        #     lev+=1
        # return lev

        # 4.bfs不記錄層高 寫在stack里
        if not root:
            return 0
        queue = [(1, root)]
        res = 1
        while queue:
            height, cur = queue.pop(0)
            if not cur.left and not cur.right:
                res = max(res, height)
            if cur.left:
                queue.append((height+1, cur.left))
            if cur.right:
                queue.append((height+1, cur.right))
        return res

105.從前序與中序遍歷序列構(gòu)造二叉樹

##1.遞歸寫法
class Solution:
    #遞歸寫法
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder and not inorder:
            return None
        
        root=TreeNode(preorder[0])
        for i in range(len(inorder)):
            if inorder[i]==preorder[0]:
                
                left_inorder=inorder[:i]
                right_inorder=inorder[i+1:]
                
                left_preorder=preorder[1:1+i]
                right_preorder=preorder[1+i:]
                
                root.left=self.buildTree(left_preorder,left_inorder)
                root.right=self.buildTree(right_preorder,right_inorder)

        return root

144.樹的前序遍歷

        # #1.遞歸寫法 48ms
        # res=[]
        # def helper(r):
        #     if not r:
        #         return None
        #     res.append(r.val)
        #     helper(r.left)
        #     helper(r.right)
        # helper(root)
        # return res

        # # 3.迭代 40ms
        # res = []
        # if not root:
        #     return res
        # s=[root]

        # while s:
        #     node=s.pop(-1)
        #     res.append(node.val)
        #     if node.right:
        #         s.append(node.right)
        #     if node.left:
        #         s.append(node.left)
        # return res

        # # 4.pythonic 遞歸 48ms
        # if not root:
        #     return []
        # return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)

        # #5.通用模板迭代 28ms
        # res=[]
        # s=[]
        # cur=root
        # while s or cur:
        #     while cur:
        #         res.append(cur.val)
        #         s.append(cur)
        #         cur=cur.left
        #     cur=s.pop(-1)
        #     cur=cur.right
        # return res

        # 6.標(biāo)記法 雙倍存儲空間磷箕，模板相同 0表示未訪問迅矛，1表示已訪問 44ms
        res = []
        s = [(0, root)]
        while s:
            flag, cur = s.pop(-1)
            if not cur:
                continue
            if flag == 0:
                s.append((0, cur.right))
                s.append((0, cur.left))
                s.append((1, cur))
            if flag == 1:
                res.append(cur.val)
        return res

236.二叉樹的最近公共祖先

當(dāng)我們用遞歸去做這個題時不要被題目誤導(dǎo)翰意，應(yīng)該要明確一點
這個函數(shù)的功能有三個：給定兩個節(jié)點 p 和 q
如果 p 和 q 都存在盗舰，則返回它們的公共祖先；
如果只存在一個渗勘，則返回存在的一個蜕该；
如果 p和 q 都不存在，則返回NULL
本題說給定的兩個節(jié)點都存在姓建，那自然還是能用上面的函數(shù)來解決

具體思路：
（1）如果當(dāng)前結(jié)點 root 等于 NULL诞仓，則直接返回 NULL
（2）如果 root 等于 p 或者 q ，那這棵樹一定返回 p 或者 q
（3）然后遞歸左右子樹速兔，因為是遞歸墅拭，使用函數(shù)后可認為左右子樹已經(jīng)算出結(jié)果，用 leftleft 和 rightright 表示
（4）此時若left為空涣狗，那最終結(jié)果只要看 right谍婉；若 right為空，那最終結(jié)果只要看 left
（5）如果 left 和 right 都非空镀钓，因為只給了 p 和 q 兩個結(jié)點穗熬，都非空，說明一邊一個丁溅，因此 root 是他們的最近公共祖先
（6）如果 left 和 right 都為空唤蔗，則返回空（其實已經(jīng)包含在前面的情況中了）

時間復(fù)雜度是 O(n)：每個結(jié)點最多遍歷一次或用主定理，空間復(fù)雜度是 O(n)：需要系統(tǒng)棧空間

#1.遞歸寫法
(遞歸) O(n)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        if not root:
            return
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and not right:
            return left
        if right and not left:
            return right
        if left and right:
            return root
        return None

#2.用dic存儲父節(jié)點
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        dic={root:None}
        def bfs(root):
            if root:
                if root.left:
                    dic[root.left]=root
                if root.right:
                    dic[root.right]=root
                bfs(root.left)
                bfs(root.right)
        bfs(root)
        l1,l2=p,q
        while(l1!=l2):
            l1=dic.get(l1) if l1 else q
            l2=dic.get(l2) if l2 else p
        return l1

543. 二叉樹的直徑

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        #  遞歸
        self.res = 0
        def getDepth(node):
            if not node:
                return 0
            le_height = getDepth(node.left)
            ri_height = getDepth(node.right)
            self.res = max(le_height+ri_height, self.res)
            return max(le_height,ri_height)+1
        getDepth(root)
        return self.res

257. 二叉樹的所有路徑

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # # 1.bfs
        # res = []
        # if not root:
        #     return res
        # queue = [(str(root.val), root)]
        # while queue:
        #     size = len(queue)
        #     for _ in range(size):
        #         path, cur = queue.pop(0)
        #         if not cur.left and not cur.right:
        #             res.append(path)
        #         if cur.left:
        #             queue.append((path+'->'+str(cur.left.val), cur.left))
        #         if cur.right:
        #             queue.append((path+'->'+str(cur.right.val), cur.right))
        # return res

        # 2.遞歸
        res=[]
        if not root:
            return res
        def helper(node,path):
            if not node.left and not node.right:
                res.append(path)
            if node.left:
                helper(node.left,path+'->'+str(node.left.val))
            if node.right:
                helper(node.right,path+'->'+str(node.right.val))
        helper(root,str(root.val))
        return res

112. 路徑總和

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # # 1.遞歸
        # if not root:
        #     return False
        # if not root.left and not root.right and root.val == targetSum:
        #     return True
        # return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

        # 2.dfs迭代
        if not root:
            return False
        stack=[(targetSum-root.val,root)]
        while stack:
            res_sum,cur=stack.pop(0)
            if not cur.left and not cur.right and res_sum==0:
                return True
            if cur.left:
                stack.append((res_sum-cur.left.val,cur.left))
            if cur.right:
                stack.append((res_sum-cur.right.val,cur.right))
        return False

572 另一棵樹的子樹

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # 1. dfs+helper
        def isTwoTreeSame(node1, node2):
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            return isTwoTreeSame(node1.left, node2.left) and isTwoTreeSame(node1.right, node2.right)

        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False

        stack = [root]
        while stack:
            cur = stack.pop(-1)
            if isTwoTreeSame(cur, subRoot):
                return True
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return False

        # # 2.兩個遞歸
        # def isTwoTreeSame(node1, node2):
        #     if not node1 and not node2:
        #         return True
        #     if not node1 or not node2:
        #         return False
        #     if node1.val != node2.val:
        #         return False
        #     return isTwoTreeSame(node1.left, node2.left) and isTwoTreeSame(node1.right, node2.right)

        # if not root and not subRoot:
        #     return True
        # if not root or not subRoot:
        #     return False
        # return isTwoTreeSame(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)```

【LeetCode】樹專題