剑指offer之(树)
树
写这个文章的目的是为了记录，好背。
树的遍历和树的深度是基础，很多题都是在遍历的基础上加些限制条件，下边题目的排序是我根据我认为的题目难度排序的，最简单基础的排在前面，一些遍历和树深度的变形题目放在后边
题目列表摆在前面：
55-I题 二叉树的深度
55-II题 平衡二叉树
28题：对称二叉树
27题：二叉树的镜像
面试题32-I 从上到下打印二叉树 I
面试题32 - II. 从上到下打印二叉树 II
面试题32 - III. 从上到下打印二叉树 III
面试题37. 序列化二叉树
面试题54. 二叉搜索树的第k大节点
面试题07. 重建二叉树
面试题34. 二叉树中和为某一值的路径
面试题68 - I. 二叉搜索树的最近公共祖先
面试题68 - II. 二叉树的最近公共祖先
面试题26. 树的子结构
面试题55 - I. 二叉树的深度
递归：
class Solution:
def TreeDepth(self, root):
# write code here
if not root:
return 0
return 1 + max(self.TreeDepth(root.left), self.TreeDepth(root.right))
迭代：
class Solution:
def TreeDepth(self, pRoot):
# write code here
depth = 0
stack = []
if pRoot:
stack.append((1, pRoot))
while stack:
curr_depth, node = stack.pop()
if node is not None:
depth = max(depth, curr_depth)
stack.append((curr_depth+1, node.left))
stack.append((curr_depth+1, node.right))
return depth
面试题55 - II. 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
class Solution:
def Permutation(self, nums):
# write code here
res = []
if not nums:
return []
nums="".join((lambda x:(x.sort(),x)[1])(list(nums)))
self.dfs(nums, '', res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in xrange(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
self.dfs(nums[:i]+nums[i+1:], path+nums[i], res)
解法2， 使用二叉树的深度做题
class Solution:
def IsBalanced_Solution(self, root):
# write code here
if not root:
return True
left = self.depth(root.left)
right = self.depth(root.right)
if abs(left-right)>1:
return False
return self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)
def depth(self, root):
if not root:
return 0
return 1 + max(self.depth(root.left), self.depth(root.right))
面试题28. 对称的二叉树
检查一棵树是否是对称二叉树
递归：
class Solution:
def isSymmetrical(self, root):
# write code here
if root is None:
return True
return self.dfs(root.left, root.right)
def dfs(self, p, q):
if p is None and q is None:
return True
if (p is None or q is None) or p.val != q.val:
return False
return self.dfs(p.left, q.right) and self.dfs(p.right, q.left)
迭代写法：
class Solution:
def isSymmetric(self, root):
if not root:
return True
stack = [(root.right, root.left)]
while stack:
r, l = stack.pop()
if not l and not r:
continue
if (not l or not r) or l.val != r.val:
return False
stack.append((l.right, r.left)) #对比左子树的右边，和右子树的左边
stack.append((l.left, r.right)) #左子树的左边，和右字数的右边
print("left: %d, right: %d"%(l.val, r.val)) #这是我测试玩的
return True
面试题27. 二叉树的镜像
输入一个二叉树，该函数输出它的镜像
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return
tmp = root.left
root.left = self.mirrorTree(root.right)
root.right = self.mirrorTree(tmp)
return root
面试题32 - I. 从上到下打印二叉树
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：[3,9,20,15,7]
提示：节点总数 <= 1000
二叉树的层次遍历， 没啥好说的。
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop(0)
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result
面试题32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：[ [3], [9,20], [15,7]]
提示：节点总数 <= 1000
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
stack = [root]
result = []
while stack:
tmp = []
for _ in range(len(stack)):
node = stack.pop(0)
tmp.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
result.append(tmp)
return result
面试题32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
stack = [root]
result = []
while stack:
tmp = []
for _ in range(len(stack)):
node = stack.pop(0)
tmp.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
result.append(tmp[::-1] if len(result) % 2 else tmp) #相比上一题就这加了个翻转的判断
return result
面试题37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
就是层次遍历的迭代写法
"""
if not root: return "[]"
queue = collections.deque()
queue.append(root)
res = []
while queue:
node = queue.popleft()
if node:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else: res.append("null")
return '[' + ','.join(res) + ']'
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
面试题54. 二叉搜索树的第k大节点
二叉树的中序遍历
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
限制：1 ≤ k ≤ 二叉搜索树元素个数
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
if not root:
return
dfs(root.right)
if self.k == 0:
return
self.k -= 1
if self.k == 0:
self.res = root.val
dfs(root.left)
self.k = k
dfs(root)
return self.res
面试题07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：0 <= 节点个数 <= 5000
解题思路
主要利用二叉树的前中后序的特性
前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序，以题目示例为例：[ 3 | 9 | 20 15 7 ]
中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序，以题目示例为例：[ 9 | 3 | 15 20 7 ]
根据题目描述输入的前序遍历和中序遍历的结果中都不含重复的数字，其表明树中每个节点值都是唯一的。
递归写法
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root = TreeNode(preorder.pop(0))
index = inorder.index(root.val)
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index+1:])
return root
迭代写法：
TODO
面试题34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[[5,4,11,2], [5,8,4,5]]
解题思路
初始化： 结果列表 res ，路径列表 path 。
返回值： 返回 res 即可。
recur(root, tar) 函数：
递推参数： 当前节点 root ，当前目标值 tar 。
终止条件： 若节点 root 为空，则直接返回。
递推工作：
路径更新： 将当前节点值 root.val 加入路径 path ；
目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 00 ）；
路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。
先序遍历： 递归左 / 右子节点。
路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def recur(root, target):
if not root:
return
path.append(root.val)
target -= root.val
if target == 0 and not root.left and not root.right:
res.append(list(path))
recur(root.left, target)
recur(root.right, target)
path.pop()
recur(root, sum)
return res
面试题68 - I. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return False
if p.val >root.val and q.val >root.val:
self. lowestCommonAncestor(root.right, p, q)
elif p.val <root.val and q.val <root.val:
self. lowestCommonAncestor(root.left, p, q)
else:
return root
面试题68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left:
return right
if not right:
return left
return root
面试题26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
解题思路
若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：
先序遍历树 A 中的每个节点 n_A 对应函数 isSubStructure(A, B)）
判断树 A 中 以 n_A 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A, B):
if not B:
return True
if not A or A.val != B.val:
return False
return recur(A.left, B.left) and recur(A.right, B.right)
return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))
