二叉树专题
0、二叉树的最大路径和
核心思路：
（1）首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
当前节点的以当前节点为起点的路径节点值最大
if not root:return 0
return root.val+max(left,right)
（2）其次，深度优先搜索的过程中更新全局最大值
maxnum=max(maxnum,root.val+left+right)
核心代码如下：
复杂度分析
参考网址：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
1、二叉树的序列化和反序列化
1）dfs
核心代码如下：
class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
flag = -1
def Serialize(self, root):
# write code here
if not root:
return '#'
else:
return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)
序列化：
递归
根左右
def Deserialize(self, s):
# write code here
self.flag=self.flag+1
lists=s.split(',')
node=None
if lists[self.flag]!='#':
node=TreeNode(int(lists[self.flag]))
node.left=self.Deserialize(s)
node.right=self.Deserialize(s)
return node
反序列化：
递归
根 左 右
相对应
注意：根节点的索引
2）bfs
核心代码如下：
class Solution:
def Serialize(self, root):
# write code here
res=[]
queue=[root]
while len(queue)>0:
tmp=queue.pop(0)
if tmp:
res.append(str(tmp.val))
queue.append(tmp.left)
queue.append(tmp.right)
else:
res.append('x')
return ','.join(res)
序列化：
宽度优先搜索：
注意空和非空都添加到数组中
def Deserialize(self, s):
if (s == 'x'):
return None
# write code here
lists=s.split(',')
root=TreeNode(int(lists[0]))
queue=[root]
cur=1
while cur<len(lists):
node=queue.pop(0)
leftval=lists[cur]
rightval=lists[cur+1]
if leftval!='x':
leftnode=TreeNode(int(leftval))
node.left=leftnode
queue.append(leftnode)
if rightval!='x':
rightnode=TreeNode(int(rightval))
node.right=rightnode
queue.append(rightnode)
cur=cur+2
return root
反序列化：
1）节点索引
2）判断是否为空值，添加左右节点
2、二叉树的右视图
（1）重建二叉树
递归
核心思路：确定左右子树
def recreate(xianxu,zhongxu):
if not xianxu or not zhongxu:
return None
rootval=xianxu[0]
root=TreeNode(rootval)
index=zhongxu.index(rootval)
root.left=recreate(xianxu[1:index+1],zhongxu[:index])
root.right=recreate(xianxu[index+1:],zhongxu[index+1:])
return root
root=recreate(xianxu , zhongxu)
（2）右视图
1）层序遍历
核心：输出每一层，把最后一个节点输出
注意每一层添加节点的时候，只添加非空节点
代码如下：
d=[root]
res=[]
res.append(root.val)
while d:
l=[]
for i in range(len(d)):
tmp=d.pop(0)
if tmp.left:
l.append(tmp.left)
if tmp.right:
l.append(tmp.right)
d=l
if l:
res.append(l[-1].val)
return res
2）递归输出右视图
核心思路：层数与右节点
递归算法核心思路
def rightsideview(root,level,path):
if not root:
return
if level>len(path):
path.append(root.val)
rightsideview(root.right,level+1,path)
rightsideview(root.left,level+1,path)
root=recreate(xianxu , zhongxu)
res=[]
rightsideview(root,1,res)
return res
参考网址：
199. 二叉树的右视图（高效方法） https://blog.csdn.net/weixin_40673608/article/details/86558877
网友评论