本系列针对面试中【经典】算法题进行分类和汇总，每篇包含两部分：基础知识和经典题目。
本文的主角是【树】。
本文结构：
-
面试前必须知道的[树]的基础知识。
-
[树]的经典手写编程题。
基础知识
基础概念
img
基础性质
img
经典面试题
- 二叉树以及二叉搜索树初始化
class Node():
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def rand_tree(self, x): #普通二叉树构建
node = Node(x)
if not self.root:
self.root = node
return
temp = [self.root]
while True:
p = temp.pop(0)
if not p.left:
p.left = node
return
elif not p.right:
p.right = node
return
temp.append(p.left)
temp.append(p.right)
def sort_tree(self, x): #搜索二叉树构建
node = Node(x)
if not self.root:
self.root = node
return
p = self.root
while True:
if x<p.val:
if not p.left:
p.left = node
return
p = p.left
elif x>=p.val:
if not p.right:
p.right = node
return
p = p.right
- 层次遍历
def traverse(root):
if not root:
return
temp = [root]
res = []
while temp:
p = temp.pop(0)
res.append(p.val)
if p.left:
temp.append(p.left)
if p.right:
temp.append(p.right)
return res
- 前序遍历
#递归版
def preoder_recursion(root):
if not root:
return []
left = preoder_recursion(root.left)
res = [root.val]
right = preoder_recursion(root.right)
return res+left+right
#非递归版
def preorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
res.append(temp[-1].val)
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
temp.append(p.right)
return res
- 中序遍历
#递归版
def inorder_recursion(root):
if not root:
return []
left = inorder_recursion(root.left)
res = [root.val]
right = inorder_recursion(root.right)
return left+res+right
#非递归
def inorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
res.append(p.val)
temp.append(p.right)
return res
- 后续遍历
#递归版
def postorder_recursion(root):
if not root:
return []
left = postorder_recursion(root.left)
res = [root.val]
right = postorder_recursion(root.right)
return left+right+res
#非递归版
def postorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
p = temp[-1]
if p.right:
temp.append(None) #用None作为分隔
temp.append(p.right)
else:
temp.append(p.right)
temp.append(p.left)
temp.pop()
if temp:
if not temp[-1]:
temp.pop()
res.append(temp.pop().val)
else:
res.append(temp.pop().val)
return res
- 重建二叉树
pre = [3,0,1,2,6,5,4,8,7,9]
mid = [0,1,2,3,4,5,6,7,8,9]
pos = [2,1,0,4,5,7,9,8,6,3]
要求不含重复数字，对于根据后序和前序遍历重建二叉树要求二叉树是搜索二叉树，不然结构不确定。
#根据前序和中序遍历
def reconstruct_1(pre, mid):
if len(pre)==0:
return None
elif len(pre)==1:
return Node(pre[0])
root = mid.index(pre[0])
flag = Node(pre[0])
flag.left = reconstruct_1(pre[1:root+1], mid[:root])
flag.right = reconstruct_1(pre[root+1:], mid[root+1:])
return flag
#根据后序和中序遍历
def reconstruct_2(pos, mid):
if len(pos)==0:
return None
elif len(pos)==1:
return Node(pos[0])
root = mid.index(pos[-1])
flag = Node(pos[-1])
flag.left = reconstruct_2(pos[:root], mid[:root])
flag.right = reconstruct_2(pos[root:-1], mid[root+1:])
return flag
#根据前序和后序遍历
def reconstruct_3(pre, pos):
print(pre)
print(pos)
if len(pos)==0:
return None
elif len(pos)==1:
return Node(pos[0])
index = pos.index(pre[1])
flag = Node(pre[0])
if index==len(pos)-2:
if flag.val<pos[0]: #判断应该在左子树还是右子树，所以要求是二叉搜索树
flag.right = reconstruct_3(pre[1:], pos[:-1])
else:
flag.left = reconstruct_3(pre[1:], pos[:-1])
else:
flag.left = reconstruct_3(pre[1:index+2], pos[:index+1])
flag.right = reconstruct_3(pre[index+2:], pos[index+1:-1])
return flag
- 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）。
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
def is_subtree(self, a, b):
if not b:
return True
if not a or a.val != b.val:
return False
return self.is_subtree(a.left, b.left) and self.is_subtree(a.right, b.right)
- 二叉树的镜像
将给定的二叉树变换为其镜像。
class Solution():
def Mirror(self, root):
if not root:
return
if not root.left and not root.right:
return
root.left, root.right = root.right, root.left
self.Mirror(root.left)
self.Mirror(root.right)
return root
- 二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
class Solution():
def FindPath(self, root, expectNumber):
if not root:
return []
if not root.left and not root.right and root.val==expectNumber:
return [[root.val]]
res = []
left = self.FindPath(root.left, expectNumber-root.val)
right = self.FindPath(root.right, expectNumber-root.val)
for i in left+right:
res.append([root.val]+i)
return res
- 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
class Solution:
def __init__(self):
self.listHead = None
self.listTail = None
def Convert(self, pRootOfTree):
if not pRootOfTree:
return
self.Convert(pRootOfTree.left)
if not self.listHead:
self.listHead = pRootOfTree
self.listTail = pRootOfTree
else:
self.listTail.right = pRootOfTree
pRootOfTree.left = self.listTail
self.listTail = pRootOfTree
self.Convert(pRootOfTree.right)
return self.listHead
- 二叉树的深度
#递归版
class Solution():
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return left+1 if left>right else right+1
#循环版
def TreeDepth(self, pRoot):
if not pRoot:
return 0
p = [pRoot]
last = p[-1]
layer = 0
while p:
p1 = p.pop(0)
if p1.left:
p.append(p1.left)
if p1.right:
p.append(p1.right)
if p1==last:
layer += 1
if p:
last = p[-1]
return layer
- 平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1，那么它就是平衡二叉树。
class Solution:
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left+1, right+1)
- 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution:
def GetNext(self, pNode):
if not pNode:
return None
if pNode.right:
p = pNode.right
while p.left:
p = p.left
return p
else:
while pNode.next:
if pNode.next.left==pNode:
return pNode.next
pNode = pNode.next
return None
- 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
（1）如果左右子树有一个为空，那么该二叉树肯定不是对称二叉树
（2）如果左右子树均不为空，但是节点的值不同，那么该二叉树肯定不是对称二叉树
class Solution:
#对称比较方法，其实也就是前序和镜像前序遍历比较的方法，和下面的对称遍历方法一个意思
def isSymmetrical(self, pRoot):
if not pRoot:
return True
if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
return False
return self.iSame(pRoot.left, pRoot.right)
def iSame(self, p1, p2):
if not p1 and not p2:
return True
if not p1 or not p2 or (p1.val!=p2.val):
return False
return self.iSame(p1.left, p2.right) and self.iSame(p1.right, p2.left)
#对称遍历方法（先存储后比较）
def isSymmetrical(self, pRoot):
if not pRoot:
return True
if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
return False
return self.preorder(pRoot) == self.preorder_n(pRoot)
def preorder(self, pRoot):
if not pRoot:
return [None]
left = self.preorder(pRoot.left)
right = self.preorder(pRoot.right)
return [pRoot.val]+left+right
def preorder_n(self, pRoot):
if not pRoot:
return [None]
left = self.preorder_n(pRoot.left)
right = self.preorder_n(pRoot.right)
return [pRoot.val]+right+left
- 按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一层按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三层按照从左到右的顺序打印，其他行以此类推。
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
res = []
res_1 = []
temp = [pRoot]
left_to_right = 1
last = temp[-1]
while temp:
p = temp.pop(0)
res_1.append(p.val)
if p.left:
temp.append(p.left)
if p.right:
temp.append(p.right)
if p==last:
res.append(res_1 if left_to_right else res_1[::-1])
left_to_right = not left_to_right
res_1 = []
if temp:
last = temp[-1]
return res
- 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
class Solution:
def Serialize(self, root):
if not root:
return '#,'
s = str(root.val) + ','
left = self.Serialize(root.left)
right = self.Serialize(root.right)
s += left + right
return s
def Deserialize(self, s):
list1 = s.split(',')
return self.deserializeTree(list1)
def deserializeTree(self, list1):
if len(list1)<=0:
return None
val = list1.pop(0)
root = None # 每次递归需要初始化，不然程序不知道是全局变量还是局部变量
if val != '#':
root = Node(int(val))
root.left = self.deserializeTree(list1)
root.right = self.deserializeTree(list1)
return root
- 二叉搜索树的第k个结点
class Solution:
def KthNode(self, pRoot, k):
if not pRoot:
return None
temp = [pRoot]
res = []
while temp:
while temp[-1]:
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
res.append(p)
temp.append(p.right)
if len(res)==k:
return res[-1]
更多干货，持续发送
网友评论