##
二叉树
递归序 每个节点都到达三次 #### 二叉树的先序、中序、后序遍历 先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树 中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树 后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点 #### 递归方式实现二叉树的先序、中序、后序遍历 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 #### 打印二叉树 #### 二叉树的宽度 求二叉树最宽的层有多少个节点 #### 找出某个节点的后继节点   二叉树结构如下定义： ```Java 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中是否存在 后序遍历递归套路 #### 派对的最大快乐值   员工信息的定义如下: ```Java class Employee { public int happy; // 这名员工可以带来的快乐值 List subordinates; // 这名员工有哪些直接下级 } ```   公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。   这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：   1.如果某个员工来了，那么这个员工的所有直接下级都不能来   2.派对的整体快乐值是所有到场员工快乐值的累加   3.你的目标是让派对的整体快乐值尽量大   给定一棵多叉树的头节点boss，请返回派对的最大快乐值。