05-30：二叉树专题

二叉树专题常见题型

1、二叉树的遍历

前、中、后：递归

层序、之字：bfs

2、二叉树的深度

（1）二叉树的深度

dfs:递归

bfs:层序遍历

（2）平衡二叉树

为空树或者左右子树高度总是相差1

核心思路：

先定义树高度函数

先判断左右子树高度差差1，再递归判断左右子树

3、树的结构/拓扑结构

（1）判断t1树中是否有与t2树拓扑结构完全相同的子树

核心思想：

先定义判断两颗树相同的函数

先判断t1树和t2树是否相同，再递归判断t1左右子树是否包含/是否和t2相同

（2）在二叉树中找到两个节点的最近公共祖先

递归的思想

1）节点为空，返回空

2）节点值为o1或o2，返回这个节点

3）递归左右子树

只有左子树找到，返回左子树

只有右子树找到，返回右子树

都找到，返回这个根节点

核心代码如下：

（3）重建二叉树

给你前序和中序遍历的结果重建二叉树

前序：根左右

中序：左根右

后序：左右根

对每一个节点，每一个子树都执行如上的顺序的访问

核心在于递归：

首先产生一个树节点

class TreeNode:

#    def __init__(self, x):

#        self.val = x

#        self.left = None

#        self.right = None

p=pre[0]

index=tin.index(p)

root=TreeNode(p)

其次递归执行，关键核心在于数组的索引确定

root.left=self.function(pre[1:index+1],tin[:index])

root.right=self.function(pre[index+1:],tin[index+1:]

最后返回节点

return root

核心代码如下：

（4）判断一棵二叉树是否为搜索二叉树和完全二叉树

搜索二叉树：中序遍历+是否递增

完全二叉树：一个为空的节点之后都是空节点

完全二叉树的核心代码思路：

把所有的节点都加入数组直至遇到第一个空节点

空节点之后判断其他是否为空节点

核心代码如下：

d=[root]

            while d and d[0]:

                    tmp=d.pop(0)

                    d.append(tmp.left)

                    d.append(tmp.right)

            while d and not d[0]:

                  d.pop(0)

            return len(d)==0

4、节点路径和

（1）二叉树中是否存在节点和为指定值的路径

递归查找

递归：是一种深度优先的算法，会一直遍历到叶子结点

递归终止：如果恰好是和值，输出True，否则输出到查到空节点，输出False

（2）二叉树根节点到叶子节点和为指定值的路径

核心代码如下：

（3）二叉树根节点到叶子节点的所有路径和

核心代码如下：

（4）二叉树的最大路径和

递归

核心在于两个变量：

1是全局变量最大值

2是当前节点下的路径和

全局最大值变量的更新是贪心算法更新

当前路径下的路径和，不能横跨，横跨之后不能连接下一个节点

核心代码如下：