06-20：刷题综合二：二叉树

二叉树专题

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