文章目錄
- 9 二叉樹
- 9.1 【遞歸】二叉樹的最大深度
- 9.2 【遞歸】相同的樹
- 9.3 【遞歸】翻轉二叉樹
- 9.4 【遞歸】對稱二叉樹
- 9.5 【遞歸】從前序與中序遍歷序列構造二叉樹
- 9.6 【遞歸】從中序與后序遍歷序列構造二叉樹
- 9.7 【BFS】填充每個節點的下一個右側節點指針 II
- 9.8 【遞歸】二叉樹展開為鏈表
- 9.9 【DFS】路徑總和
- 9.10 【DFS】求根節點到葉節點數字之和
- 9.11 【BFS】【動態規劃】二叉樹中的最大路徑和
- 9.12 【BFS】二叉搜索樹迭代器
- 9.13 【BFS】完全二叉樹的節點個數
- 9.14 【遞歸】二叉樹的最近公共祖先
- 10 二叉樹層次遍歷
- 10.1 【DFS】二叉樹的右視圖
- 10.2 【BFS】二叉樹的層平均值
- 10.3 【BFS】二叉樹的層序遍歷
- 10.4 【BFS】二叉樹的鋸齒形層序遍歷
- 11 二叉搜索樹
- 11.1 【BFS】二叉搜索樹的最小絕對差
- 11.2 【BFS】二叉搜索樹中第K小的元素
- 11.3 【BFS】【遞歸】驗證二叉搜索樹
9 二叉樹
9.1 【遞歸】二叉樹的最大深度
題目地址：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
??遞歸找左子樹和右子樹的最大深度，就是二叉樹的最大深度。
# 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 = rightclass Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0else:left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)return max(left_depth, right_depth) + 1
9.2 【遞歸】相同的樹
題目地址：https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150
??左右子樹相同的標志是左右子樹都存在，且根節點的值相等，按照這一標準遞歸遍歷樹的左右子樹。
# 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 = rightclass Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:if (not p and q) or (p and not q):return Falseelif not p and not q:return Trueelif p.val != q.val:return Falseelse:return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
9.3 【遞歸】翻轉二叉樹
題目地址：https://leetcode.cn/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:returnroot.left,root.right = self.invertTree(root.right),self.invertTree(root.left)return root
9.4 【遞歸】對稱二叉樹
題目地址：https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truereturn self.is_symmetric(root.left, root.right)def is_symmetric(self, left: TreeNode, right: TreeNode):if not left and not right:return Trueelif (not left or not right) or (left.val != right.val):return Falseelse:return self.is_symmetric(left.left, right.right) and self.is_symmetric(left.right, right.left)
9.5 【遞歸】從前序與中序遍歷序列構造二叉樹
題目地址：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼，找到根節點的位置進行遞歸。
# 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 = rightclass Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder or not inorder:returnroot = TreeNode(preorder[0])idx = inorder.index(preorder[0])root.left = self.buildTree(preorder[1:1+idx],inorder[:idx])root.right = self.buildTree(preorder[1+idx:],inorder[idx+1:])return root
9.6 【遞歸】從中序與后序遍歷序列構造二叉樹
題目地址：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼，找到根節點的位置進行遞歸。
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:if not inorder or not postorder:returnroot = TreeNode(postorder[-1])idx = inorder.index(postorder[-1])root.left = self.buildTree(inorder[:idx],postorder[:idx])root.right = self.buildTree(inorder[1+idx:],postorder[idx:-1])return root
9.7 【BFS】填充每個節點的下一個右側節點指針 II
題目地址：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150
??其實就是找出每一層的所有結點就行了，而每一層的左右節點就是下一層的結點，按照這個規則進行BFS。
"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootdef BFS(curLayer):nextLayer = []for node in curLayer:if node.left:nextLayer.append(node.left)if node.right:nextLayer.append(node.right)if len(nextLayer) > 1:for i in range(0,len(nextLayer)-1):nextLayer[i].next = nextLayer[i+1]if nextLayer:BFS(nextLayer)BFS([root])return root
9.8 【遞歸】二叉樹展開為鏈表
題目地址：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150
??二叉樹的先序遍歷的變形。
# 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 = rightclass Solution:def flatten(self, root: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead."""while root:if root.left:cur_left = root.leftwhile cur_left.right:cur_left = cur_left.rightcur_left.right = root.rightroot.right = root.leftroot.left = Noneroot = root.right
9.9 【DFS】路徑總和
題目地址：https://leetcode.cn/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return Falseelif not root.left and not root.right and targetSum == root.val:return Trueelse:return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
9.10 【DFS】求根節點到葉節點數字之和
題目地址：https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150
??DFS，分別從根節點計算每一條路徑的數字，然后求和，這里要注意判斷條件，當一個節點沒有左節點和右節點時，說明這條路徑到底了，這是要把目前的數字加入到 a n s ans ans中。
# 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 = rightclass Solution:def sumNumbers(self, root: Optional[TreeNode]) -> int:ans = 0def sub_sum(root,cur_num):nonlocal ansif not root.left and not root.right:ans += cur_num*10 + root.valreturncur_num = cur_num*10 + root.valif root.left:sub_sum(root.left,cur_num)if root.right:sub_sum(root.right,cur_num)sub_sum(root,0)return ans
9.11 【BFS】【動態規劃】二叉樹中的最大路徑和
題目地址：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150
??先找到每個節點下的最大路徑和，再一步步從上往下遍歷所有節點，如果遍歷到某個節點的左子樹或者右子樹的最大和小于零，則這個子樹可以不要，只需考慮另一個子樹即可。
# 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 = rightclass Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:self.maxSum = -1001def BFS(root):if not root:return 0left_max = BFS(root.left)right_max = BFS(root.right)self.maxSum = max(self.maxSum, left_max + right_max + root.val)return max(0,max(left_max,right_max) + root.val)BFS(root)return self.maxSum
9.12 【BFS】二叉搜索樹迭代器
題目地址：https://leetcode.cn/problems/binary-search-tree-iterator/description/?envType=study-plan-v2&envId=top-interview-150
??先對二叉搜索樹中的元素進行排序，然后按照題目要求構造函數即可。
# 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 = rightclass BSTIterator:def __init__(self, root: Optional[TreeNode]):self.root = rootself.num = []self.idx = 0self.len = 0def BFS(root):if not root:returnself.num.append(root.val)self.len += 1BFS(root.left)BFS(root.right)BFS(root)self.num.sort()def next(self) -> int:if self.idx < self.len:self.idx += 1return self.num[self.idx-1]else:return -1def hasNext(self) -> bool:if self.idx < self.len:return Trueelse:return False# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
9.13 【BFS】完全二叉樹的節點個數
題目地址：https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def countNodes(self, root: Optional[TreeNode]) -> int:self.ans = 0def BFS(root):if not root:returnself.ans += 1BFS(root.left)BFS(root.right)BFS(root)return self.ans
9.14 【遞歸】二叉樹的最近公共祖先
題目地址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
??如果 p p p和 q q q位于二叉樹的同一側，那么最近公共祖先要么是 p p p要么是 q q q，如果位于二叉樹的兩側，那么最近公共祖先則是兩者最深的那個 r o o t root root。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if not left:return rightif not right:return leftreturn root
10 二叉樹層次遍歷
10.1 【DFS】二叉樹的右視圖
題目地址：https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150
??深度優先遍歷，每次都將二叉樹每一層最右邊的元素加入數組，同時設置 d e p t h depth depth來限制數組大小，保證數組中只有最右邊的元素。
# 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 = rightclass Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:self.ans = []def DFS(root, depth):if not root:returnif len(self.ans) < depth:self.ans.append(root.val)DFS(root.right, depth+1)DFS(root.left, depth+1)DFS(root, 1)return self.ans
10.2 【BFS】二叉樹的層平均值
題目地址：https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:ans = []node_list = [root]if not root:return answhile node_list:cur_val = []nxt_list = []for node in node_list:cur_val.append(node.val)if node.left:nxt_list.append(node.left)if node.right:nxt_list.append(node.right)ans.append(sum(cur_val)/len(cur_val))node_list = nxt_listreturn ans
10.3 【BFS】二叉樹的層序遍歷
題目地址：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:ans = []cur_node = [root]if not root:return answhile cur_node:cur_val = []nxt_node = []for node in cur_node:cur_val.append(node.val)if node.left:nxt_node.append(node.left)if node.right:nxt_node.append(node.right)ans.append(cur_val)cur_node = nxt_nodereturn ans
10.4 【BFS】二叉樹的鋸齒形層序遍歷
題目地址：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150
??詳見代碼。
# 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 = rightclass Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:ans = []cur_node = [root]flag = Trueif not root:return answhile cur_node:cur_val = []nxt_node = []for node in cur_node:cur_val.append(node.val)if node.left:nxt_node.append(node.left)if node.right:nxt_node.append(node.right)if flag:ans.append(cur_val)else:ans.append(cur_val[::-1])flag = not flagcur_node = nxt_nodereturn ans
11 二叉搜索樹
11.1 【BFS】二叉搜索樹的最小絕對差
題目地址：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150
??先遍歷所有節點，然后排序，找出相鄰元素差值最小的。
# 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 = rightclass Solution:def getMinimumDifference(self, root: Optional[TreeNode]) -> int:self.num = []def BFS(root):if not root:returnself.num.append(root.val)BFS(root.left)BFS(root.right)BFS(root)self.num.sort()ans = 100001for i in range(len(self.num)-1):ans = min(ans,self.num[i+1]-self.num[i])return ans
11.2 【BFS】二叉搜索樹中第K小的元素
題目地址：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150
??對于二叉搜索樹而言，中序遍歷就是其從小到大的排序結果，記錄訪問到的第 k k k個元素即可。
# 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 = rightclass Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:self.k = kself.ans = 0def BFS(root):if not root:returnBFS(root.left)self.k -= 1if self.k == 0:self.ans = root.valreturnBFS(root.right)BFS(root)return self.ans
11.3 【BFS】【遞歸】驗證二叉搜索樹
題目地址：https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150
??遞歸實現，首先要明白二叉搜索樹的判定條件，一是左子樹<root<右子樹，二是下面的左子樹的值要比當前結點小，而右子樹的值要比當前結點大，也就是不能只在一個小的子樹上滿足這個條件，往上回溯幾代之后這個條件要依然滿足才行。
# 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 = rightclass Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def is_Valid_BST(root, min_node, max_node):if not root:return Trueelse:if min_node and root.val <= min_node.val:return Falseif max_node and root.val >= max_node.val:return Falsereturn is_Valid_BST(root.left, min_node, root) and is_Valid_BST(root.right, root, max_node)return is_Valid_BST(root, None, None)
