Leetcode【700、872、897、965、1022】
- 2019 年 10 月 29 日
- 筆記
問題描述：【Tree】700. Search in a Binary Search Tree 解題思路：
這道題是給一棵二叉搜索樹（BST），查找給定的結點。結點不存在返回 NULL。
利用 BST 的特點，進行二分查找即可。
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def searchBST(self, root: TreeNode, val: int) -> TreeNode: if not root: return None if root.val == val: return root elif root.val > val: return self.searchBST(root.left, val) elif root.val < val: return self.searchBST(root.right, val)
問題描述：【Tree】872. Leaf-Similar Trees 解題思路：
這道題是給兩棵樹，判斷它們的葉子序列（從左到右）是否相同。
將兩棵樹的葉子序列保存在 list 中，判斷二者是否相同即可。
1、判斷葉子的條件是 root.left == None and root.right == None，返回 [root.val]； 2、還要注意單子樹的情況（[1, 2] 或 [1, null, 2]），應該返回 []；
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool: def leafSeq(root): # 得到樹的葉子序列 if not root: # 防止單子樹（如 [1,2] 或者 [1,null,2]） return [] if root.left == None and root.right == None: # 葉子 return [root.val] return leafSeq(root.left) + leafSeq(root.right) return leafSeq(root1) == leafSeq(root2)
問題描述：【Tree】897. Increasing Order Search Tree 解題思路：
這道題是給一棵二叉搜索樹，將結點按照從小到大重新排列，構造一棵只有右結點的樹。
先前序遍歷將每個結點保存在 list 中，再構造只有右結點的樹。構造右結點的樹時，除了根結點 node 外，還要有一個工作指針 cur，在遍歷 list 的過程中，cur 每次往右子樹走（cur = cur.right），最後返回 node 即可。
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def increasingBST(self, root: TreeNode) -> TreeNode: def in_order(root): # 中序遍歷，保存結點 if not root: return [] return in_order(root.left) + [TreeNode(root.val)] + in_order(root.right) nodelist = in_order(root) node = cur = nodelist[0] # node:指向根結點，cur：往右子樹走 for i in range(1, len(nodelist)): cur.right = nodelist[i] cur = cur.right return node
問題描述：【Tree】965. Univalued Binary Tree 解題思路：
這道題是給一棵二叉樹，判斷其是否是單值二叉樹（所有結點值都相同）。
1、先將根結點的值作為目標值 tar，將 tar 也參與遞歸函數； 2、如果 root 為 None，返回 True； 3、如果 root.val == tar，就遞歸左右子樹，返回左右子樹的判斷結果； 4、否則返回 False。
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isUnivalTree(self, root: TreeNode) -> bool: if not root: return True self.tar = root.val # 目標值 return self.judge(root) def judge(self, root): if root == None: return True if root.val == self.tar: return self.judge(root.left) and self.judge(root.right) return False
問題描述：【DFS、Tree】1022. Sum of Root To Leaf Binary Numbers 解題思路：
這道題是給一個 01 二叉樹，計算從根到葉子所有二進制路徑表示的十進制數字的總和。
方法1（回溯法）：
第一種容易想到的方法就是 DFS 回溯法，對樹進行深度優先搜索，將每條路徑 path 保存在 paths 列表中，每次找到一條路徑的出口是遇到葉子結點。最後，對 paths 進行遍歷，將每條路徑 path 中的二進制轉化為十進制數進行累加（如 int("0101", 2) = 5）。這樣做的空間複雜度為 O(n)。
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sumRootToLeaf(self, root: TreeNode) -> int: def findPath(root, path): if not root: return path += str(root.val) # 往當前路徑中添加當前結點 if root.left == None and root.right == None: # 到葉子結點，增加一條路徑 paths.append(path) return findPath(root.left, path) findPath(root.right, path) paths, sum = [], 0 # paths 保存每條路徑 findPath(root, "") for path in paths: sum += int(path, 2) # 二進制轉十進制 return sum
方法2（不使用額外空間的做法）：
有沒有不使用額外空間的做法呢？當然有。可以使用前綴和 presum。
在深度優先搜索的過程中，每增加一層，就修改當前路徑的累加值，即 presum = presum * 2 + root.val，如 1->0->1 （5）再碰到 1 就會執行 presum = presum * 2 + 1 = 11，剛好是 1->0->1->1（11）。
具體做法如下： 1、如果 root 為空，返回 0； 2、更新前綴累加和 presum = presum * 2 + 1； 2、如果 root.left 或者 root.right 不為空，就遞歸求解左右子樹路徑和 return pathSum(root.left, presum) + pathSum(root.right, presum)； 3、最後返回 presum 就是答案；
Python3 實現：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sumRootToLeaf(self, root: TreeNode) -> int: def pathSum(root, presum): if not root: return 0 presum = presum * 2 + root.val # 每增加一層修改當前路徑累加值 if root.left or root.right: # 左右子樹路徑之和 return pathSum(root.left, presum) + pathSum(root.right, presum) return presum # 到葉子結點 return pathSum(root, 0)
