#定义树节点的数据结构
class TreeNode:
def __init__(self,x):
self.val = x
self.left = None
self.right = None
前序和后续确定一棵二叉树前序遍历和非递归遍历中序的遍历和非递归遍历后续的遍历和非递归遍历层次遍历找两个节点的最近邻公共祖先树的镜像判断B是不是A的子树计算树的高度求节点双亲求节点的孩子节点求二叉树叶子节点个数判断两棵二叉树是否相同求先序遍历中的第k个节点判断树是否为平衡树
#1、根据前序遍历和中续遍历构造二叉树
def create_Tree(pre,tin):
if not pre or not tin:
return None
root = TreeNode(pre.pop(0))
index = tin.index(root.val)
root.left = create_Tree(pre,tin[:index])
root.right = create_Tree(pre,tin[index+1:])
return root
#2、前序遍历
def Print_pre(root):
if root:
print(root.val)
Print_pre(root.left)
Print_pre(root.right)
#3、前序非递归遍历
def Print_pre_no(root):
stack = []
p = root
while p or stack:
if p:
print(p.val, end=",")
stack.append(p)
p = p.left
else:
p = stack.pop()
p = p.right
#4、非递归中序遍历
def Print_mid(root):
stack = []
p = root
while p or stack:
if p:
stack.append(p)
p = p.left
else:
p = stack.pop()
print(p.val,end=",")
p = p.right
#5、非递归的后序遍历 后序遍历的结果是先序遍历中对左右子树互换位置得来的
def Print_afer(root):
stack = []
p = root
result = []
while p or stack:
if p:
result.append(p.val)
stack.append(p)
p = p.right
else:
p = stack.pop()
p = p.left
print(result[::-1])
后序遍历的时候，一定要标记是从左孩子返回的还是右孩子返回的，如果是从右孩子返回的即可访问根，用标记的思想实现后序遍历算法：
def aft_Pre(root):
if not root:
return
stack = []
node = root
MarkNode = None
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if not node.right or node.right is MarkNode:
print(node.val,end = ",")
MarkNode = node
node = None
else:
stack.append(node)
node = node.right
典型的使用两个栈：
def aft_print(root):
stack1 = []
stack2 = []
node = root
stack1.append(node)
while stack1:
node = stack1.pop()
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
stack2.append(node)
for i in stack2:
print(i.val)
#6、找两个节点的最近邻公共祖先，p和q，设定p在q节点的左面
在后序遍历的时候，当遍历到p节点时，栈中的节点都是p的祖先节点。故用这个思想，我们借助两个栈，当遍历到p节点时，将此时栈中的节点全部拷贝到另一个栈中，继续遍历，直到遇到q节点，然后将两个栈中的节点从栈顶开始匹配，最先匹配上的节点就是最近邻祖先节点。
def LatestParents(root,p,q):
stack = []
stack1 = []
MarkNode = None
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if not node.right or node.right is MarkNode:
if node.val == p.val:
stack1 = stack[::-1]
if node.val == q.val:
stack = stack[::-1]
for i in stack:
for j in stack1:
if i.val == j.val:
return i.val
return
MarkNode = node
node = None
else:
stack.append(node)
node = node.right
#7、层次遍历
def Print_level(root):
CurrentLineNode = [root]
line = 0
while root and CurrentLineNode:
NextLineNode = []
#everLineNodeVal = []
for node in CurrentLineNode:
if node.left:
NextLineNode.append(node.left)
if node.right:
NextLineNode.append(node.right)
#everLineNodeVal.append(node.val)
print("第%d行的节点"%(line))
for i in CurrentLineNode:
print(i.val,end=",")
print()
#print(everLineNodeVal)
line = line + 1
CurrentLineNode = NextLineNode
#打印之字型
#使用三个列表，当前行的节点currentlineNode，下一行的节点nextLineNode，还有保存每一行节点val的 everLineNode，判断当前行的节点list是否为空，不空的话为下一行做准备，把当前行里的节点的非空左右孩子放在下一行的节点list中，同时保存上当前行的节点，遍历完当前行所有节点，更新当前行为下一行，继续上面操作
def Print(pRoot):
# write code here
result = []
line = 0
currentlineNode = [pRoot]
while pRoot and currentlineNode:
everLineNode = []
nextLineNode = []
for node in currentlineNode:
if node.left:
nextLineNode.append(node.left)
if node.right:
nextLineNode.append(node.right)
everLineNode.append(node.val)
line = line + 1
if line % 2 == 0:
result.append(everLineNode[::-1])
else:
result.append(everLineNode)
currentlineNode = nextLineNode
return result
#8、树的镜像，将树的左右孩子颠倒位置
它是采用栈实现的非递归，根据层次遍历来的，但是少一层循环，因为他不需要区分每一层节点。
#递归实现
def Mirror(root):
if root:
root.left,root.right = root.right,root.left
Mirror(root.left)
Mirror(root.right)
#非递归实现
def Mirror(root):
# write code here
if not root:
return
stack = [root]
while stack:
node = stack.pop(0)
if node.left or node.right:
node.left,node.right = node.right,node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
#9、输入两棵树A,B，判断B是不是A的子树（空树不是任意一棵树的子结构）
用递归来实现，从A树的根节点开始，判断其所有的节点是不是依次和树B相同，如不同，递归调用函数，继续判断树A当前节点的左子树的所有节点或右子树的所有节点是否和树B所有节点相同，直到遍历到父树A的叶子节点，如果不是完全相同，则树B不是树A子树，如果直到遍历到树B的叶子节点，其所有节点在树A中均有，则树B是树A的子树。
def HassubTree(rootA,rootB):
if not rootA or not rootB:
return False
return isSubTree(rootA,rootB) or HassubTree(rootA.left,rootB) or HassubTree(rootA.right,rootB)
def isSubTree(root1,root2):
if not root2:
return True
if not root1:
return False
if root1.val == root2.val:
return isSubTree(root1.left,root2.left) and isSubTree(root1.right,root2.right)
return False
#10、计算树的高度
后序遍历算法
def After_pre(root):
if not root:
return 0
else:
leftH = After_pre(root.left)
rightH = After_pre(root.right)
return max(leftH,rightH)+1
#判断一棵树是否是平衡二叉树
def After_pre(root):
if not root:
return 0
else:
leftH = After_pre(root.left)
rightH = After_pre(root.right)
return max(leftH,rightH)+1
def isAvarTree(root):
if not root:
return True
if abs(After_pre(root.left) - After_pre(root.right)) > 1:
return False
else:
return isAvarTree(root.left) and isAvarTree(root.right)
面试经典上面的原题
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Balance:
def TreeHigh(self,root):
if not root:
return 0
else:
leftH = self.TreeHigh(root.left)
rightH = self.TreeHigh(root.right)
return max(leftH,rightH)+1
def isBalance(self, root):
# write code here
if not root:
return True
if abs(self.TreeHigh(root.left) - self.TreeHigh(root.right)) > 1:
return False
else:
return self.isBalance(root.left) and self.isBalance(root.right)
#创建 树（二叉排序树、完全二叉树、平衡树）
pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
root = create_Tree(pre,tin)
Print_pre(root)#前序遍历递归调用
Print_level(root)#层次遍历调用
Print_pre_no(root)#前序遍历的非递归调用
Print_mid(root)#中序遍历的非递归调用
Print_after(root)#后序遍历的非递归调用
Print_level(root)#层次遍历调用
root = Mirror(root)#树的镜像
Print_level(root)#层次遍历输出树的镜像
def duichen_binary(root):
if not root:
return False
currentNode = [root]
while currentNode:
nextLineNode = []
valline = []
for i in currentNode:
if i == ' ':
valline.append(' ')
continue
if i.left:
nextLineNode.append(i.left)
else:
nextLineNode.append(' ')
if i.right:
nextLineNode.append(i.right)
else:
nextLineNode.append(' ')
valline.append(i.val)
if len(valline)>1:
a = 0
b = len(valline) - 1
while a < b:
if valline[a] != valline[b]:
return False
else:
a = a + 1
b = b - 1
currentNode = nextLineNode
