解题思路：
这道题是给一棵二叉搜索树（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)
解题思路：
这道题是给两棵树，判断它们的叶子序列（从左到右）是否相同。
将两棵树的叶子序列保存在 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)
解题思路：
这道题是给一棵二叉搜索树，将结点按照从小到大重新排列，构造一棵只有右结点的树。
先前序遍历将每个结点保存在 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
解题思路：
这道题是给一棵二叉树，判断其是否是单值二叉树（所有结点值都相同）。
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
解题思路：
这道题是给一个 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)
