問(wèn)題描述：【Tree】700. Search in a Binary Search Tree
解題思路：
這道題是給一棵二叉搜索樹（BST）母谎，查找給定的結(jié)點(diǎn)。結(jié)點(diǎn)不存在返回 NULL京革。
利用 BST 的特點(diǎn)销睁，進(jìn)行二分查找即可。
Python3 實(shí)現(xiàn)：
# 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)
問(wèn)題描述：【Tree】872. Leaf-Similar Trees
解題思路：
這道題是給兩棵樹存崖，判斷它們的葉子序列（從左到右）是否相同冻记。
將兩棵樹的葉子序列保存在 list 中，判斷二者是否相同即可来惧。
1冗栗、判斷葉子的條件是 root.left == None and root.right == None，返回 [root.val]；
2隅居、還要注意單子樹的情況（[1, 2] 或 [1, null, 2]）钠至，應(yīng)該返回 []；
Python3 實(shí)現(xiàn)：
# 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)
問(wèn)題描述：【Tree】897. Increasing Order Search Tree
解題思路：
這道題是給一棵二叉搜索樹胎源，將結(jié)點(diǎn)按照從小到大重新排列棉钧，構(gòu)造一棵只有右結(jié)點(diǎn)的樹。
先前序遍歷將每個(gè)結(jié)點(diǎn)保存在 list 中涕蚤，再構(gòu)造只有右結(jié)點(diǎn)的樹宪卿。構(gòu)造右結(jié)點(diǎn)的樹時(shí)，除了根結(jié)點(diǎn) node 外万栅，還要有一個(gè)工作指針 cur佑钾，在遍歷 list 的過(guò)程中，cur 每次往右子樹走（cur = cur.right）烦粒，最后返回 node 即可休溶。
Python3 實(shí)現(xiàn)：
# 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): # 中序遍歷，保存結(jié)點(diǎn)
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:指向根結(jié)點(diǎn)扰她，cur：往右子樹走
for i in range(1, len(nodelist)):
cur.right = nodelist[i]
cur = cur.right
return node
問(wèn)題描述：【Tree】965. Univalued Binary Tree
解題思路：
這道題是給一棵二叉樹兽掰，判斷其是否是單值二叉樹（所有結(jié)點(diǎn)值都相同）。
1徒役、先將根結(jié)點(diǎn)的值作為目標(biāo)值 tar禾进，將 tar 也參與遞歸函數(shù)；
2廉涕、如果 root 為 None泻云，返回 True；
3狐蜕、如果 root.val == tar宠纯，就遞歸左右子樹，返回左右子樹的判斷結(jié)果层释；
4婆瓜、否則返回 False。
Python3 實(shí)現(xiàn)：
# 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 # 目標(biāo)值
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
問(wèn)題描述：【DFS贡羔、Tree】1022. Sum of Root To Leaf Binary Numbers
解題思路：
這道題是給一個(gè) 01 二叉樹廉白，計(jì)算從根到葉子所有二進(jìn)制路徑表示的十進(jìn)制數(shù)字的總和。
方法1（回溯法）：
第一種容易想到的方法就是 DFS 回溯法乖寒，對(duì)樹進(jìn)行深度優(yōu)先搜索猴蹂，將每條路徑 path 保存在 paths 列表中，每次找到一條路徑的出口是遇到葉子結(jié)點(diǎn)楣嘁。最后磅轻，對(duì) paths 進(jìn)行遍歷珍逸，將每條路徑 path 中的二進(jìn)制轉(zhuǎn)化為十進(jìn)制數(shù)進(jìn)行累加（如 int("0101", 2) = 5）。這樣做的空間復(fù)雜度為 O(n)聋溜。
Python3 實(shí)現(xiàn)：
# 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) # 往當(dāng)前路徑中添加當(dāng)前結(jié)點(diǎn)
if root.left == None and root.right == None: # 到葉子結(jié)點(diǎn)谆膳，增加一條路徑
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) # 二進(jìn)制轉(zhuǎn)十進(jìn)制
return sum
方法2（不使用額外空間的做法）：
有沒(méi)有不使用額外空間的做法呢？當(dāng)然有撮躁。可以使用前綴和 presum漱病。
在深度優(yōu)先搜索的過(guò)程中，每增加一層把曼，就修改當(dāng)前路徑的累加值杨帽，即 presum = presum * 2 + root.val，如 1->0->1 （5）再碰到 1 就會(huì)執(zhí)行 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 實(shí)現(xiàn)：
# 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 # 每增加一層修改當(dāng)前路徑累加值
if root.left or root.right: # 左右子樹路徑之和
return pathSum(root.left, presum) + pathSum(root.right, presum)
return presum # 到葉子結(jié)點(diǎn)
return pathSum(root, 0)
