二叉树相关内容总结

关于二叉树的一些总结（将继续更新）
跟树相关的题目一般都跟先序遍历、中序遍历、后序遍历、层次遍历有关。
1.二叉树重构

• 一般来说，对于节点数值不存在相等的情况下，先+中、后+中序遍历完全可以对二叉树进行重构，而先+后是不能对二叉树进行重构的，究其原因在于:先序：根左右 后序：左右根，左右不分家，问题出在这里，假设某个子树缺少左子树或者右子树，那么在重构时不能确定该左/右子树是原来的左右子树中的哪一个。但是，知道了问题所在，那么对于不含这种问题的二叉树，即真二叉树（内部节点都有两孩子），那么采用先+后序遍历是可以对真二叉树进行重构的(Tsinghua OJ:真二叉树重构)。既然真二叉树可以采用这种方式重构，那么完全二叉树、满二叉树也可以通过这种方式重构。
• 上述重构的假设前提是：二叉树节点val值不能存在相等的情况，(举个简单例子{3,3,#}和{3,#,3}),这是一个缺点；除此之外，这种重构方法在只有全部读取两个序列的数据后才能开始进行重构(剑指offer P195)。牛客剑指题目 序列化二叉树 ，无非就是遍历时将空节点也标记进来，这样就只用一种遍历方式即可将节点、空节点连续存储以便后续的重构。原则上来说，序列化二叉树选择何种遍历方式都可以将二叉树进行重构，但是考虑到效率问题，如果希望在序列开始输入就可以进行重构，那么最好选择先序遍历，因为这样存储的序列根节点在最开始位置。至于层次遍历暂未思考...