6.5 KiB
二叉树
递归序 每个节点都到达三次
二叉树的先序、中序、后序遍历
先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树 中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树 后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点
递归方式实现二叉树的先序、中序、后序遍历
1）理解递归序 2）先序、中序、后序都可以在递归序的基础上加工出来 3）第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序
X 祖先节点 交集
X是一棵二叉树的某一个节点，A是二叉树先序遍历X的左边部分，B是二叉树后序遍历X右边部分，AB相交的结果是且仅是X的所有父节点。 1、X的所有父节点在先序遍历的左边，X的所有父节点在后序遍历的右边，交集一定包含所有父节点 2、X的所有子节点在先序遍历的左边，X的所有子节点在后序遍历的左边，交集一定不包含所有子节点 3、A不包含所有祖先节点的右兄弟节点，B不包含所有祖先节点的左兄弟节点 X的所有祖先节点、X自己、X的子节点、X或者X的父节点作为左树的右兄节点、X或者X的父节点作为右树的左兄节点
非递归方式实现二叉树的先序、中序、后序遍历
1）任何递归函数都可以改成非递归 2）自己设计压栈的来实现
实现二叉树的按层遍历
1）其实就是宽度优先遍历，用队列 2）可以通过设置flag变量的方式，来发现某一层的结束
实现二叉树的序列化和反序列化
1）先序方式序列化和反序列化 2）按层方式序列化和反序列化
将多叉树编码为二叉树 LeetCode431
打印二叉树
二叉树的宽度
求二叉树最宽的层有多少个节点
找出某个节点的后继节点
二叉树结构如下定义：
Class Node {
V value;
Node left;
Node right;
Node parent;
}
给你二叉树中的某个节点，返回该节点的后继节点。
折纸
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。 例如:N=1时，打印: down N=2时，打印: down down up
主要解题思路是递归
二叉树的递归套路 1）假设以X节点为头，假设可以向X左树和X右树要任何信息 2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要） 3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息 4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S 5）递归函数都返回S，每一棵子树都这么要求 6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
判断两颗二叉树是否相同 LeetCode100
判断一个二叉树是否对称 LeetCode101
获取一个二叉树的高度 LeetCode104
用先序数组和中序数组重建一个二叉树 LeetCode105
先序遍历的第一个元素是头结点，先序遍历剩余部分左边是左节点的先序，右边是右节点的先序，中序遍历左边是左节点的中序，右边是右节点的中序。递归构建二叉树，递归函数入参为先序遍历的起止index，中序遍历的起止index，返回头结点。
二叉树按层遍历收集节点 LeetCode107 LeetCode102
使用LinkedList(有序，快速插入)，递归将每一层的节点入队、出队。
平衡二叉树 LeetCode110
给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树 判断二叉树是否是平衡二叉树 左子树的高度和右子树的高度相差不超过1，则称为平衡二叉树。
搜索二叉树 LeetCode98
判断二叉树是否是搜索二叉树 递归解决
路径总和 LeetCode112
达标路径总和 LeetCode113
二叉树的最大距离
给定一颗二叉树的头结点，任何两个节点之间都存在距离，返回整颗二叉树的最大距离。
判断完全二叉树
判断二叉树是否是完全二叉树 按照二叉树的定义判断，逐行遍历 递归套路
满二叉树
给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树
最大的二叉搜索子树
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点。
最大的二叉搜索子树大小
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小。
最低公共祖先
给定一棵二叉树的头节点head，和另外两个节点a和b。返回a和b的最低公共祖先。 a、b可能在head的左右子树，也可能在同一棵子树。 使用中间变量 1、遍历整棵树，用map保存所有节点的父节点 2、遍历a的所有父节点，用set保存 3、遍历b的所有父节点，看set中是否存在 后序遍历递归套路
派对的最大快乐值
员工信息的定义如下:
class Employee {
public int happy; // 这名员工可以带来的快乐值
List<Employee> subordinates; // 这名员工有哪些直接下级
}
公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则： 1.如果某个员工来了，那么这个员工的所有直接下级都不能来 2.派对的整体快乐值是所有到场员工快乐值的累加 3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。