9. 在二叉树中找到一个节点的后继节点

每个节点都遍历三遍

1）先序遍历（头左右）在第一次遍历到节点的时候打印

2）中序遍历（左头右）在第二次遍历到节点的时候打印

3）后序遍历（左右头）在第三次遍历到节点的时候打印

1）从栈中弹出一个节点

2）打印（处理）弹出的节点

3）先右在左放入栈中

后序遍历是左右头，先序遍历是头左右->根据上面压栈方式是先右后左

那么如果我们先左后右，先序遍历就会变成头右左，在通过栈的处理就变成了左右头，也就是后序遍历

1）每颗子树，整颗树左边界进站

2）弹出打印、处理

3）弹出的右边界进站

整棵树都是可以被左边界分解掉

左头右（左头）

调用下面的函数可以图形化显示你的二叉树

题目：求一颗二叉树的最大宽度

问题拆分，需要知道遍历的节点处于第几层

不用hashmap

题目：如何判断一颗二叉树是否是搜索二叉树？

左树小，右树大

中序遍历，一定都是升序

题目：如何判断一颗二叉树是完全二叉树？

满的，最后一层从左到右是满的

宽搜

1）任何一个节点只有右侧没有左侧，直接false。

2）在1）条件下，如果遇到了第一个左右子不全，后续皆为叶子节点。

题目：如何判断一颗二叉树是满二叉树？

第一种麻烦的方法：获得最大深度，节点个数，根据关系判断是否是满二叉树

题目：如何判断一颗二叉树是否是平衡二叉树？（二叉树题目套路）

平衡二叉树：左、右高度差为1

整理左右树的信息：平衡？高度？

题目：如何判断一颗二叉树是否是搜索二叉树？（2）

整理条件：

树型DP

题目：如何判断一颗二叉树是满二叉树？（2）

总结：套路是一棵树的节点能够向左右要相同的信息解决的题都可以这样做。应用于各种树形DP

往上最初汇聚的点

本质是二叉树的中序遍历，生成一颗不存在的二叉树