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)
