给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
一、解题思路
上图中标出的坐标中，前为行号，后为列号，本题实质上就是排序。本题排序规则为：列号从小到大；对于同列结点，按照行号从小到大；对于同行同列结点，按数值从小到大。
因此对该树遍历一遍，遍历同时记录每个节点的（col, row, value），遍历完成后，按照col为第一关键字升序，row为第二关键字升序，value为第三关键字升序，对所有结点进行排序。那如何记录结点信息呢，数组和哈希表都可以。
二、代码+复杂度 // map键为结点，值为一数组
private Map<TreeNode, int[]> map = new HashMap<>();
public List<List<Integer>> verticalTraversal(TreeNode root) {
// 初始化根结点 {col, row, val}
map.put(root, new int[]{0, 0, root.val});
// 递归作用是将每个节点的三元组信息存入map中
dfs(root);
// map的values是数组，就是把所有结点的信息存入list中
List<int[]> list = new ArrayList<>(map.values());
//
Collections.sort(list, (a, b)->{
if(a[0] != b[0]) return a[0] - b[0];
if(a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
// 返回值列表，存放遍历序列
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < list.size(); ) {
int j = i;
// temp列表存放同列的结点的值（按从小到大）
List<Integer> temp = new ArrayList<>();
while(j < list.size() && list.get(j)[0] == list.get(i)[0]){
temp.add(list.get(j++)[2]);
}
// 本列结束后，将本列结点值添加到res中
res.add(temp);
// 下一循环的i从j开始，i就跳过了列值相同的结点，来到下一个列值迭代
i = j;
}
return res;
}
public void dfs(TreeNode root){
if(root == null) return;
int[] info = map.get(root);
int col = info[0], row = info[1], val = info[2];
// 记录当前root的左孩子坐标三元组
if(root.left != null){
map.put(root.left, new int[]{col-1, row+1, root.left.val});
dfs(root.left);
}
// 记录当前root的右孩子坐标三元组
if(root.right != null){
map.put(root.right, new int[]{col+1, row+1, root.right.val});
dfs(root.right);
}
}
复杂度分析：
- 时间复杂度：填充哈希表时进行树的遍历，复杂度为$O(N)$，其中$N$为为树中节点的数目。构造答案时需要进行排序，复杂度为$O(nlogn)$，整体复杂度为$O(nlogn)$。
- 空间复杂度：$O(N)$。
专题：二叉树路径 687. 最长同值路径
687、最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
这题可以使用后序递归，从叶节点开始找，直到根结点。思考每个结点要做的同样的事是什么？遍历到当前root时，递归左右子树，左右子树都返回一个值，此值是以root为根，且包含root值本身所在的单侧最长同值路径长度。以当前root为根，看左子树和右子树的值是否和root的值一样，左右子树返回值相加就是以root为根时的最长路径。依次遍历所有结点，寻找最大路径长度。
二、算法流程 三、代码+复杂度代码：
class Solution {
private int maxLen = 0;
public int longestUnivaluePath(TreeNode root) {
// 空树，即[]，同值最长路径为0
if(root == null) return 0;
dfs(root, root.val);
return maxLen;
}
public int dfs(TreeNode root, int value){
// 到达根结点，往上层返回0
if(root == null) return 0;
// 本题可以采用后序遍历，从下往上找
//
int left = dfs(root.left, root.val);
int right = dfs(root.right, root.val);
// 路径长度为节点数减1所以此处不加1
maxLen = Math.max(maxLen, left + right);
// 当前root的值为value，和父节点值相同才返回以当前节点所能构成的最长
// 同值路径长度, 否则返回0
if(root.val == value){
return Math.max(left, right) + 1;
}
return 0;
}
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$是树中节点数，每个结点遍历一次；
- 空间复杂度：$O(H)$，$H$是树的深度，递归调用栈可以达到$H$层的深度；
124. 二叉树的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
看到二叉树问题，首先思考采用什么遍历方式，递归还是迭代？递归的话每个结点干什么事？
- 求路径问题，几乎都是递归了。
- 这种求路径和问题，不从根开始的话，一般都是后序递归了。
- 每个结点要算
Math.max(maxRes, leftSum + rightSum + root.val)这个值的大小跟当前最大值maxRes比是否最大。
此题关键点在于：在以当前root为根的子树中寻找以root为起点的一条路径，使得该路径上的结点值之和最大（要么在root的左子树中，要么在root的右子树中），算法如下：
- 维护一个全局变量
maxSum存储最大路径和，递归时更新maxSum. - 后序递归左右子树，从根开始，返回值分别是以当前root为根时，左右子树的最长路径。左右子树路径和为负值不考虑，置0表示不取为负值的左或右子树
- 单次递归处理：
- 判断当前root包含左右子树之和是否大于当前最大路径
maxSum； - 当前root递归完后的返回值：返回以root为根节点的二叉树的左或右子树中和最大的那一条路径；
- 判断当前root包含左右子树之和是否大于当前最大路径
private int maxRes = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxRes;
}
public int dfs(TreeNode root){
if(root == null){
return 0;
}
// 左右子树路径和为负值不考虑，置0表示不取为负值的左或右子树
int leftSum = Math.max(0, dfs(root.left));
int rightSum = Math.max(0, dfs(root.right));
// 后序遍历 单次递归处理
// 判断当前root包含左右子树之和是否大于当前最大路径
maxRes = Math.max(maxRes, leftSum + rightSum + root.val);
// 返回以root为根节点的二叉树的左右子树中和最大的那一条路径
return Math.max(leftSum, rightSum) + root.val;
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$是中二叉树中节点数，每个结点遍历一次；
- 空间复杂度：$O(N)$，其中$N$是中二叉树中节点数，空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。
测试用例：{-10,22,20,#,#,15,7}，输出值为47，测试网站：牛客
863. 二叉树中所有距离为 K 的结点
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
一、解题思路
这道题没什么思路，看了下官方题解。第一步先用map集合保存每个结点的父结点（因为对于target，路径长度为K肯定要去父结点找）；第二步直接从target结点开始，沿着三条路径（左、右、父）依次递归，递归时传入一个参数len表示当前结点距离target的长度，递一次则长度len+1，每次递归需要再记录一个from变量，表示上一层递归的结点是哪个。递归终止条件是空节点时返回上层，当len == k时返回上层。
二、算法流程为什么需要一个from？
对于上图中的例子，结点5先向左子树走，来到6，然后向父亲走，又来到5，虽然k=2，但不符合题意。再比如，k=3，从结点5开始，可行的路径有5-->3-->1-->3，刚好3步，但3并不是所求结点。所以每次遍历到一个地方，就要记录它上一步从何而来，不走回头路。
算法可分为两步：
-
先用map集合保存每个结点的父结点（递归实现）；
public void findParents(TreeNode root){ if(root.left != null){ // 有左孩子，存入map，则key为左孩子val，value为root（父亲） parentsMap.put(root.left.val, root); findParents(root.left); } if(root.right != null){ parentsMap.put(root.right.val, root); findParents(root.right); } } -
从target开始递归，并维护一个
from结点记录上层访问的结点，防止走回头路；- 遇到空节点，返回上层
- 当
len == k时，当前结点加入res，返回上层 - 访问左孩子寻找长度为k的结点
- 访问右孩子寻找长度为k的结点
- 访问父结点寻找长度为k的结点
private List<Integer> res = new ArrayList<>();
Map<Integer, TreeNode> parentsMap = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// 第一步，从root出发进行DFS，记录每个结点的父结点
findParents(root);
// 第二步，从target出发DFS，寻找所有路径长度为k的结点
dfs(target, null, 0, k);
return res;
}
// node从targe开始，递归node的左、右、父三个分支，当前遍历到node，且长度为k，加入res。
public void dfs(TreeNode node, TreeNode from, int len, int k){
if(node == null) return;
// 路径长度为2，找到了一个，把node加入res
if(len == k){
res.add(node.val);
return;
}
// 从target开始，访问左孩子寻找长度为k的结点
if(node.left != from){
dfs(node.left, node, len + 1, k);
}
// 访问右孩子寻找长度为k的结点
if(node.right != from){
dfs(node.right, node, len + 1, k);
}
// 访问父结点寻找长度为k的结点
if(parentsMap.get(node.val) != from){
dfs(parentsMap.get(node.val), node, len + 1, k);
}
}
public void findParents(TreeNode root){
if(root.left != null){
// 有左孩子，存入map，则key为左孩子val，value为root（父亲）
parentsMap.put(root.left.val, root);
findParents(root.left);
}
if(root.right != null){
parentsMap.put(root.right.val, root);
findParents(root.right);
}
}
注：其实也可以不用设形参len，即每次递归时让k-1即可，递归出口改成if(k==0)...也行。
牛客测试，测试用例：{3,5,1,6,2,0,8,#,#,7,4}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。需要执行两次DFS操作，每次的时间复杂度均为$O(N)$.
- 空间复杂度：$O(N)$，记录父结点需要$O(N)$的map空间，DFS需要$O(N)$的栈空间。
865. 具有所有最深节点的最小子树
一、解题思路给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
一个节点的 子树 是该节点加上它的所有后代的集合。
返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
本题要求的是一棵子树，该子树包含所有最深的结点（叶节点），让我想到了求“两节点的最近公共祖先”。先找出所有最深的结点，再找出包含所有最深的结点的最小子树。官方解法一就是这样。
然并卵，之后看了一个思路，卧槽牛逼！一棵树如果左右子树高度相同则根节点就是最小子树，如果不是一样高，则最小子树一定在高的一边，向高的一边递归就行了。
输入一棵树，输出的最深两节点的最近公共祖先。采用前序遍历（不要被代码中递归求高度舞而误导为是后序递归），从根结点开始，一直到叶结点结束。单次递归流程：
- 分别计算以当前结点为根的左子树和右子树的高度（含当前结点），
- 如果高度一样，则说明当前结点就是要求的点；
- 如果高度不等，则去高度大的子树继续判断（最深的结点就在这子树中）。
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root == null){
return root;
}
// 求当前结点的左右子树高度（含当前结点）
int leftMaxDepth = getMaxDepth(root.left);
int rightMaxDepth = getMaxDepth(root.right);
// 左右高度相等，说明最深的结点在cur左右两边，该结点就是要求的点
if(leftMaxDepth == rightMaxDepth){
return root;
}
// 如果左子树高，就去左子树找最小子树
if(leftMaxDepth > rightMaxDepth){
return subtreeWithAllDeepest(root.left);
}
// 否则，就去右子树找
return subtreeWithAllDeepest(root.right);
}
// 求树的高度
public int getMaxDepth(TreeNode root){
if(root == null){
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return (left > right ? left : right) + 1;
}
牛客测试，测试用例：{3,5,1,6,2,0,8,#,#,7,4}，输出：{2,7,4}
复杂度分析：
- 时间复杂度：$O(N^2)$，其中$N$为为树中节点的数目。每次到新的结点都要递归求它的左右子树的高度，存在冗余计算。
- 空间复杂度：$O(N)$，递归栈所用空间最大为$N$。
988. 从叶结点开始的最小字符串
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）
一、解题思路
本题考查二叉树路径问题。可以从根结点开始，不断向下遍历，中途经过的结点所代表的字符加入到sb（StringBuilder类）中，一直到叶节点。到达叶节点，将sb逆序并转化为字符串（从叶到根的路径），把该字符串同之前的最小值res（初始设为无穷大）进行比较，小的话就赋值给res。比较完成后，还要把sb翻转回来，用于后面结点的递归。【注意：递归返回上层时sb的值是不变的，故需要对sb进行翻转处理，此外，本结点递归完后，要从右边返回上层父结点，那么本层结点就要在sb中抹掉，以保证遍历到其他根结点时sb中存的是根到叶的路径】
二、代码+复杂度 // 这里设定"~"表示无穷大，~的ascii码为126
String res = "~";
public String smallestFromLeaf(TreeNode root) {
dfs(root, new StringBuilder());
return res;
}
public void dfs(TreeNode root, StringBuilder sb){
if(root == null) return;
// char加int的结果是int（本题说了a是0，b是1...），再把int转为char加入到sb中
sb.append((char)('a' + root.val));
if(root.left == null && root.right == null){
// 到达叶节点，将sb反序，并转化为字符串
sb.reverse();
String s = sb.toString();
// compareTo()的返回值是整型，它是先比较对应字符的大小（ASCII码顺序）
// 如果第一个字符和参数的第一个字符不等，结束比较，返回他们之间的差值
// 如果第一个字符和参数的第一个字符相等，则以第二个字符和参数的第二个字符作比较
// 这里就是只要s比res小，就把s赋给res
if(s.compareTo(res) < 0)
res = s;
// sb第一次翻转是为了赋给res，第二次翻转是为了再返回上层继续递归
sb.reverse();
}
// 前序遍历
dfs(root.left, sb);
dfs(root.right, sb);
//当前root结束，要回到上层递归调用处，故sb要去掉当前root的结点，即sb中最后一个字符
sb.deleteCharAt(sb.length()-1);
}
str.compareTo(String anotherString): 按字典顺序比较两个字符串，返回值为int。 比较是基于字符串中每个字符的Unicode值。
复杂度分析：
- 时间复杂度：使用$O(N)$的复杂度来遍历整棵树，其中$N$为为树中节点的数目，然后调整字符串内容sb，每轮翻转与比较的时间复杂度为$O(L)$，其中$L$是到达叶节点时候得到字符串的长度（二叉树的高度，平衡二叉树中$L=log(N)$），时间复杂度为$O(Nlog(N))$.
- 空间复杂度：$O(N)$，取决于递归栈的空间。
专题：二叉搜索树 700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
本题就是二叉搜索树的查找操作，根据二叉搜索树的性质：左<根，根<右。我们可以建立递归查询某结点并返回。
二、算法流程利用二叉排序树的特性，前序递归查找目标值
- 从根结点开始，比较目标值和
root.val的大小；val < root.val，则说明目标值val存在的话必然在root的左子树val > root.val，则说明目标值val存在的话必然在root的右子树val = root.val，直接返回结果；
// 递归法
public TreeNode searchBST(TreeNode root, int val) {
if(root == null) return null;
if(root.val == val){
return root;
} else if(val < root.val){
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
// 迭代法
public TreeNode searchBST(TreeNode root, int val) {
while(root != null){
if(val < root.val){
root = root.left;
} else if(val > root.val){
root = root.right;
} else{
return root;
}
}
return null;
}
复杂度分析：
- 时间复杂度：递归和迭代都是$O(N)$，其中$N$是二叉搜索树的节点个数，最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要迭代$N$次。
- 空间复杂度：递归的空间复杂度为$O(N)$，因最坏情况下递归需要$O(N)$的栈空间。迭代法空间复杂度为$O(1)$，没有使用额外空间。
783. 二叉搜索树节点最小距离
给你一个二叉搜索树的根节点
root，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
二叉搜索树中序遍历有序，差值很小的一般都是连续的结点之间才会存在。可以在中序遍历该二叉树时计算当前结点和上一结点的差值（必然为正）。用一个全局变量来记录最小差值，直到遍历到中序最后一个结点。
其实最简单的思路就是将中序遍历结果存到一个list中，然后依次计算相邻元素的差值，取最小的那个即可。
二、算法流程 见解题思路。
三、代码+复杂度// 递归法
private TreeNode pre = null;
private int minRes = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
dfs(root);
return minRes;
}
public void dfs(TreeNode root){
if(root == null){
return ;
}
/** 中序遍历模板 */
dfs(root.left);
// 遍历同时将当前结点减去上一结点，并和minRes比大小
if(pre != null){
minRes = Math.min(minRes, root.val - pre.val);
}
// 计算完后，pre指针后移
pre = root;
dfs(root.right);
}
// 迭代法
public int minDiffInBST(TreeNode root) {
TreeNode pre = null;
int minRes = Integer.MAX_VALUE;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || stack.size() > 0){
// while结束，cur指向最左下结点的左孩子（是个空节点）
while(cur != null){
stack.push(cur);
cur = cur.left;
}
// 栈顶出栈
cur = stack.pop();
if(pre != null){
minRes = Math.min(minRes, cur.val - pre.val);
}
pre = cur;
cur = cur.right;
}
return minRes;
}
可以观察两种方式，都是在中序遍历模板内添加以下两句代码即可实现。
if(pre != null) minRes = Math.min(minRes, cur.val - pre.val); pre = cur;
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$是中二叉树中节点数，每个节点在中序遍历中都会被访问一次且只会被访问一次；
- 空间复杂度：$O(N)$，递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 $O(N)$级别。
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
从根节点开始，通过BST的性质，要插的比根大去右边找，要插的比根小去左边找，循环结束后，就找到了要插节点的位置，并且还要记录要插入的前驱（父结点），比前驱值大就插在前驱右边，比前驱值小就插在前驱左边。
参考解题思路。
三、代码+复杂度 // 迭代法
public TreeNode insertIntoBST(TreeNode root, int val) {
// 空树直接插入即可
if(root == null) {
root = new TreeNode(val);
return root;
}
// 构造工作指针 pre是要插的前驱，node是待插节点，cur为工作指针
TreeNode pre = null;
TreeNode node = new TreeNode(val);
TreeNode cur = root;
// while结束，就找到了要插入的位置，此时cur为null，
while(cur != null){
pre = cur;
if(val < cur.val){
cur = cur.left;
} else if(val > cur.val){
cur = cur.right;
}
}
// 循环结束后，看是否比前驱大，比前驱小则插在左边，比前驱大则插在右边
if(val < pre.val){
pre.left = node;
}
if(val > pre.val){
pre.right = node;
}
return root;
}
递归法：
public TreeNode insertIntoBST(TreeNode root, int val) {
// 空树或到达叶子结点，构建插入节点，返回
if(root == null){
root = new TreeNode(val);
return root;
}
// 插入的值比root的值小，插入到左子树上面，递归的返回值是构造的空节点或子树
if(val < root.val){
root.left = insertIntoBST(root.left, val);
}
// 插入的值比root的值大，插入到右子树上面，递归的返回值是构造的空节点或子树
if(val > root.val){
root.right = insertIntoBST(root.right, val);
}
return root;
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。最坏情况下，我们需要将值插入到树的最深的叶子结点上，而叶子节点最深为$O(N)$。
- 空间复杂度：$O(1)$，只使用了常数大小的空间。
450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
删除二叉搜索树的结点，有三种情况：
- 删除叶子节点
- 删除叶子节点不会破坏
BST的结构，直接置空；
- 删除叶子节点不会破坏
- 删除带有一个孩子的节点
- 将待删除节点的左/右子树 赋值给 待删除节点的父节点的左/右子树；（右空左补，左空右补）
- 删除带两个孩子的节点
- 左右孩子都存在，中序后续填补
从根结点开始遍历，当查询值比根结点小（大），就去根结点左（右）边找，不断递归，直到找到要查询的值。找到之后，要分解题思路中的三种情况：
-
左子树不空，右子树空，则删除root，用右子树填补root
-
右子树不空，左子树空，则删除root，用左子树填补root
-
左右子树都不空，那用中序后继节点填补（这种情况也要细分为两种情况）
-
后继节点无右孩子，则直接把后继节点的值赋给root，删除后继节点
-
后继节点有右孩子，则直接把后继节点的值赋给root，将
root.right（图中是10号）这个节点的左指针指向后继节点的右孩子（9号），这个过程涉及到单链表操作，要用指针处理。
-
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return null;
if(key < root.val){
root.left = deleteNode(root.left, key);
} else if(key > root.val){
root.right = deleteNode(root.right, key);
} else{
// 此时key等于当前结点
if(root.left == null){
return root.right;
}
if(root.right == null){
return root.left;
}
// root的左右孩子都有，中序后续填补
// 找中序后序方法：去右子树中找最左结点
TreeNode p = root.right;
TreeNode pre = root; // pre用来保存p的前驱（有删除p的操作）
//循环结束，p来到最左结点（p指向root的中序后继）
while(p.left != null){
pre = p;
p = p.left;
}
// 替换并连接
root.val = p.val;
// 这个if说明while执行了，即待删结点root的右孩子有左子树，
if(p != root.right){
pre.left = p.right;
} else{
// while没有执行，root的右孩子没左子树，删root，root的右子树取代root
pre.right = p.right;
}
}
return root;
}
代码中if和else的两种情况：
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(H)$，递归时堆栈使用的空间，$H$是树的高度。
897. 递增顺序搜索树
给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
一、解题思路
法一：
二叉搜索树，中序遍历，得到有序序列，然后对有序序列遍历建立链表，此方法需要申请额外辅助空间来存储遍历得到的序列。
法二：
上面的方法保存了整个中序遍历序列，比较浪费空间，那么只需要一个变量prev保存遍历时的上一次被访问的结点即可。在每次遍历时：
- 把当前结点root.left设置为null；
- 把prev.right设置为当前遍历的结点root；
- prev指向root；
见解题思路。
三、代码+复杂度 List<TreeNode> list = new ArrayList<>();
public TreeNode increasingBST(TreeNode root) {
inorder(root);
// 这里也可以设置一个空的头结点，一般把值设为-1，然后返回的是头结点下一个结点
TreeNode head = list.get(0);
TreeNode cur = head;
for(int i = 1; i < list.size(); i++){
// 要将左子树置空
cur.right = list.get(i);
cur.left = null;
cur = cur.right;
}
// 最后一个节点的左子树也要置空
cur.left = null;
// 返回根结点
return head;
}
public void inorder(TreeNode root){
if(root == null) return ;
inorder(root.left);
list.add(root);
inorder(root.right);
}
------------------------------- 方法二 ---------------------------------------
TreeNode prev = null;
public TreeNode increasingBST(TreeNode root) {
// 设立一个头结点，值为-1
TreeNode head = new TreeNode(-1);
prev = head;
dfs(root);
return head.right;
}
public void dfs(TreeNode root){
if(root == null) return;
/** 中序遍历 */
dfs(root.left);
// 每次遍历时，把当前root左设为null，前驱指向当前root，
root.left = null;
prev.right = root;
prev = root;
dfs(root.right);
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：
938. 二叉搜索树的范围和
给定二叉搜索树的根结点
root，返回值位于范围[low, high]之间的所有结点的值的和。
中序遍历BST，定义一个全局变量保存结果值，判断当前值是否在low和high之间，在的话就加上当前结点值，不断按中序递归。
另外，还有一个思路，直接从根结点开始查找结点值在low和high之间的值，当前结点比low小就去右子树中找，当前结点比high大就去左子树中找。
另外，也可使用BFS迭代法，定义一个队列，从根节点开始找。那么有三种情况：
- 根大于high，则把根的左孩子入队；
- 根小于low，则把根的右孩子入队；
- 否则，sum += cur.left, 再把cur的左右孩子入队
直接看解题思路。
三、代码+复杂度class Solution {
int res = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
if(root == null) return 0;
dfs(root, low, high);
return res;
}
// 递归累加求和即可
public void dfs(TreeNode root, int low, int high){
if(root == null) return;
dfs(root.left, low, high);
if(root.val >= low && root.val <= high){
res += root.val;
}
dfs(root.right, low, high);
}
}
// -------------------- 法二 --------------------------------
public int rangeSumBST(TreeNode root, int low, int high) {
// 不要全局变量法
if(root == null) return 0;
// 从根结点开始判断，依据根大于左，小于右
if(root.val >= low && root.val <= high){
// 当前结点在low和high之间，则把当前结点加到结果值，并往左右子树递归
return root.val + rangeSumBST(root.left, low, high) +
rangeSumBST(root.right, low, high);
} else if(root.val < low){
// 当前结点小于low，往右子树中找
return rangeSumBST(root.right, low, high);
} else{
// 当前结点大于high，往左子树中找
return rangeSumBST(root.left, low, high);
}
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(N)$，空间复杂度主要取决于栈空间的开销。
专题：二叉树重构 814. 二叉树剪枝
给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。
一、解题思路
意思是说，以当前root为根时，其子树没有一个结点为1的，那么就可以删除root和root的子树了。半天没想出来怎么搞，看了一眼别人的代码，后序递归，去掉叶节点中所有的0结点，返回值为null，见0是叶节点就删。这思想牛皮！
二、算法流程 后序递归解法，从叶节点开始，删除0结点（0结点置空），不断递归，删除叶节点中的0结点即可。
三、代码+复杂度 public TreeNode pruneTree(TreeNode root) {
if(root == null){
return null;
}
// 注意递归返回值
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// 0是根结点，往上层返回null，相当于删除0
if(root.left == null && root.right == null && root.val == 0){
return null;
}
// 否则，返回root
return root;
}
牛客测试用例{1,0,1,0,0,0,1}，输出{1,#,1,#,1}。
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(H)$，其中$H$是树的高度，为我们在递归时使用的栈空间大小。
889. 根据前序和后序遍历构造二叉树
一、解题思路返回与给定的前序和后序遍历匹配的任何二叉树（其中一个）。
pre和post遍历中的值是不同的正整数。示例：
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
此题和前中序建立二叉树和后中序建立二叉树不同，要想建树唯一，中序必须已知，否则构建的二叉树不唯一。
前序遍历的特点是根节点始终出现在第一位；后序遍历的特点是根节点始终出现在最后一位。如下图，前序遍历第一个元素是根节点，后面的那一堆就是左子树，接着是右子树；而后序遍历第一个出现的是左子树，然后是右子树，最后才是根节点。所以，只要能确定橙色部分的范围，就可以处理左子树了，而左子树范围确定了，那么顺带右子树也就可以搞定了。
二、算法流程
- 用前序遍历的第一个元素创建出根节点；
- 用前序遍历的第二个元素
x，去后序遍历中找对应的下标y，将y+1就能得到左子树的个数了 - 将前序数组，后序数组拆分左右两部分
- 递归的处理前序数组左边、后序数组左边
- 递归的处理前序数组右边、后序数组右边
- 返回根节点
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
if(preorder.length == 0 || postorder.length == 0){
return null;
}
return dfs(preorder, 0, preorder.length - 1, postorder, 0, postorder.length-1);
}
public TreeNode dfs(int[] pre, int preL, int preR, int[] post, int postL, int postR){
if(preL > preR || postL > postR){
return null;
}
// 构建根节点
TreeNode root = new TreeNode(pre[preL]);
// 左右指针相遇，返回上层
if(preL == preR){
return root;
}
int index;
// pre[preL+1]是左子树的根，找到该值在后序数组中的索引
for(index = postL; index <= postR; index++){
if(post[index] == pre[preL+1]){
break;
}
}
// 循环结束，index指向根结点在后序序列某位置
int left_len = index - postL + 1;
int right_len = postR - index;
// 左子树非空，构建左子树
if(left_len > 0){
root.left = dfs(pre, preL + 1, preL+1+left_len-1, post, postL, index);
}
// 右子树非空，构建右子树
if(right_len > 0){
root.right = dfs(pre, preL+left_len+1, preR, post, index+1, postR - 1);
}
return root;
}
复杂度分析：
- 时间复杂度：$O(N2)$，其中$N$为为树中节点的数目。递归执行N次，因为每次递归都在当前长度上减少了一个根节点，所以需要N次。每次递归会执行for循环索引后序遍历数组，故为$O(N2)$。
- 空间复杂度：$O(N)$，调用栈的内存，最坏情况下深度为$N$。
894. 所有可能的满二叉树
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
一、解题思路
本题中所定义的“满二叉树”和数据结构中的定义不同，不要搞混。本题利用递归来解，观察上例，把7个节点分成3部分（左根右），可能的组合有（1，1，5），（3，1，3），（5，1，1）三种。对于5个结点，可能的组合有（1，1，3），（3，1，1）两种。对于3个结点，可能的组合有（1，1，1）一种。那么，我们可以递归构建左右子树，每次递归传入的参数就是左子树的节点个数i或右子树的结点个数n-i-1，其中i必为奇数，递归返回值为集合，
二、算法流程- 递归边界：
- 当n=1时，即左或右子树只有1个结点，加入到res中，为后面排列组合做准备；
- 如果输入是一个偶数，偶数节点不可能构成满二叉树，返回一个空列表。
- 用一个循环，找到所有可能的左右子树的可能的数量的情况，把root放进列表里
allPossibleFBT(i)返回了一个列表，当结点数为i时，存放着所有满足条件的左子树的集合；allPossibleFBT(n-1-i)存放着所有满足条件的右子树的集合；- 接下来，就是左右子树的排列组合，一共有
right.size()*left.size()种可能，对于左子树有i个结点，右子树有n-1-i个结点时，我们把所有可能的树加入list中
public List<TreeNode> allPossibleFBT(int n) {
List<TreeNode> res = new ArrayList<>();
// 偶数节点不可能构成满二叉树
if(n % 2 == 0){
return res;
}
// n为1，建立结点
if(n == 1){
TreeNode root = new TreeNode(0);
res.add(root);
}
// 分别左右建树，把奇数n拆成 奇数+1+奇数（左+根+右）
for(int i = 1; i < n; i += 2){
// 左子树有i个节点，返回一个列表，存放着结点数为i时，所有满足条件root集合
List<TreeNode> left = allPossibleFBT(i);
// 当前传进来的n是此时左根右结点总数，n减去左减去根就是右子树的个数
List<TreeNode> right = allPossibleFBT(n - i - 1);
// 建树，左右子树的排列组合左1右1，左3右1，左1右3，左1右5，左5右1
for(TreeNode l : left){
for(TreeNode r : right){
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
复杂度分析：
- 时间复杂度：$O(2^N)$，其中$N$给定树结点的数目。
- 空间复杂度：$O(2^N)$
专题：两树判断相似 872. 叶子相似的树
一、解题思路请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为root1和root2的树是叶相似的，则返回 true；否则返回 false 。
本题还算简单，只需要前序递归遍历两棵树，碰到叶子节点就把结点存到预先申请的list集合中，再判断两list集合是否大小相等（不等直接返回false），再依次判断两list的对应值是否相等。
二、算法流程 可以使用深度优先搜索的方法得到一棵树的「叶值序列」,具体地，在深度优先搜索的过程中，我们总是先搜索当前节点的左子节点，再搜索当前节点的右子节点。如果我们搜索到一个叶节点，就将它的值放入序列中。在得到了两棵树分别的「叶值序列」后，我们比较它们是否相等即可。
三、代码+复杂度 public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
dfs(root1, list1);
dfs(root2, list2);
if(list1.size() != list2.size()) return false;
for(int i = 0; i < list1.size(); i++){
if(list1.get(i) != list2.get(i)) return false;
}
return true;
}
public void dfs(TreeNode root, List<Integer> list){
if(root == null) return;
// 前序遍历模板
if(root.left == null && root.right == null){
list.add(root.val);
}
dfs(root.left, list);
dfs(root.right, list);
}
复杂度分析：
- 时间复杂度：$O(n1+n2)$，其中$n1$和$n2$分别是两棵树中节点的数目。
- 空间复杂度：$O(n1+n2)$，空间复杂度主要取决于存储「叶值序列」的list空间以及深度优先搜索的过程中需要使用的栈空间。
951. 翻转等价二叉树
我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。
编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。
一、解题思路
思想：如果二叉树 root1，root2 根节点值相等，那么只需要检查他们的孩子是不是相等就可以了。
采用前序递归来判断，root1和root2指针应该同步移动，分析下每个结点单次递归应该做什么事？有三种情况：
- 如果
root1或者root2是null，那么只有在他们都为null的情况下这两个二叉树才等价。 - 如果
root1，root2的值不相等，那这两个二叉树的一定不等价。 - 如果以上条件都不满足，也就是当 root1 和 root2 的值相等的情况下，需要继续判断 root1 的孩子节点是不是跟 root2 的孩子节点相当。因为可以做翻转操作，所以这里有两种情况需要去判断。
- 如果该结点的左右孩子未发生翻转，则左右孩子的值必然一样，同步判断两棵树的左结点、右结点是否相等；
- 如果该结点的左右孩子发生了翻转，则左右孩子的值颠倒，同步判断树1中该结点的左（右）孩子是否等于树2中该结点的右（左）孩子。
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
// 两个都为null才返回true
if(root1 == null && root2 == null){
return true;
}
// root1和root2有一个不空，则不等价
if(root1 == null || root2 == null){
return false;
}
// 同时判断root1和root2的左右子树 或者 判断root1的左（右）和root2的右（左）子树
// 如果同时判左右或同时判一左一右，两个有一个满足，即可返回true
if(root1.val == root2.val){
return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) || flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
}
// 其他情况都返回false
return false;
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
958. 二叉树的完全性检验
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1--$2^h$ 个节点。
采用BFS层序遍历的思想，设置一个bool型变量，来记录遍历过程中是否碰到了空节点。如果当前出队为空节点，则修改标志位为true；如果当前出队不为空，且之前没遇到空节点，就把当前结点的左右孩子入队。
二、代码+复杂度 public boolean isCompleteTree(TreeNode root) {
if(root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode cur;
// 初始化flag为false，记录遍历过程中是否遇到空节点
boolean flag = false;
while(queue.size() > 0){
// 出队
cur = queue.poll();
// 如果出队结点为null，则把falg置为true
if(cur == null) {
flag = true;
} else {
// 出队结点不为null，并且之前遍历到了空节点，那肯定不是完全二叉树
if(flag == true) return false;
// 出队结点的左右孩子入队，无论是否为空
queue.offer(cur.left);
queue.offer(cur.right);
}
}
return true;
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(N)$，其中$N$为为树中节点的数目。
专题：二叉树判断 965. 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回
true；否则返回false。
一、解题思路
本题其实有很多种解法。DFS递归法、前序递归+列表法、层序BFS法。
DFS递归法，从根节点开始，每个结点要判断的是左右孩子是否存在，如果存在就看结点的值是否等于左右孩子的值，只要不等于就返回false，递归判断左右子树即可。
前序递归+列表法，首先定义一个列表存储前序遍历序列，然后使用一个for循环判断列表中的值是否都是同一个即可。
层序BFS法，借助辅助空间队列，当结点的左右孩子存在且左右孩子的值和根结点的值保持一样就把对应左右孩子入队即可。
二、代码+复杂度 public boolean isUnivalTree(TreeNode root) {
if(root == null) return true;
if(root.left != null && root.val != root.left.val){
return false;
}
if(root.right != null && root.val != root.right.val){
return false;
}
boolean left = isUnivalTree(root.left);
boolean right = isUnivalTree(root.right);
return left && right;
}
// -------------------------------------------------
public boolean isUnivalTree(TreeNode root) {
if(root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(queue.size() > 0){
TreeNode cur = queue.poll();
if(cur.left != null ){
if(cur.val == cur.left.val){
queue.offer(cur.left);
} else {
return false;
}
}
if(cur.right != null){
if(cur.val == cur.right.val){
queue.offer(cur.right);
} else {
return false;
}
}
}
return true;
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：递归DFS时空间复杂度为$O(H)$，BFS层序时空间复杂度为$O(N)$。
971. 翻转二叉树以匹配先序遍历
给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。
另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。
通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：
请翻转 最少 的树中节点，使翻转后的二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。
如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。
一、解题思路
这题目太长了，具体意思是：输入为一棵树和一个先序遍历序列voyage，翻转该树中的结点（翻转时只需要交换当前结点的左右子树即可，其他节点的关系不变），使得翻转后的树走一遍前序遍历，得到的序列就是voyage，那么输出为翻转的结点的值的列表。
可以使用前序遍历来遍历当前这棵树，遍历的同时把当前root的值同voyage对应的下标值voyage[i]比较是否相等，
- 如果不相等说明
该树不管怎么翻转，永远也不能匹配voyage。 - 如果相等则再比较当前root的左孩子的值（非空时）是否不等于voyage[i+1]，不等于的话说明可以把当前root的左右子树进行交换试试，（所用到的思想是：前序遍历的下一结点永远是左孩子，前提是左孩子存在时）
- 交换完左右子树后，把当前root加入res返回列表
- 然后递归判断下一个结点，那么voyage中的下标i也要不断自增。
二叉树遍历完成后，看标志位flag是否为true。flag=true说明了该树不管怎么翻转，永远也不能匹配voyage，返回-1列表；flag=false说明了该树翻转再先序遍历可以得到voyage序列，返回要翻转的值列表即可。
二、代码+复杂度class Solution {
int i = 0; //记录voyage的位置
boolean flag; //记录树的行程与给定的行程 voyage 是否相匹配
List<Integer> res = new ArrayList<>();
public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
dfs(root, voyage);
// 只要dfs时flag为true了，则该树不管怎么翻转，永远也不能匹配voyage，返回-1列表
if(flag == true){
List<Integer> ans = new ArrayList<>();
ans.add(-1);
return ans;
}
return res;
}
public void dfs(TreeNode root, int[] voyage) {
// 空节点返回上层
if(root == null) return;
// 当前root不等于先序遍历的指定节点（如根结点），则该树不管怎么翻转，永远也不能匹配
// voyage
if(root.val != voyage[i]){
flag = true;
return;
}
// 当前root有左孩子，但左孩子不是先序遍历的下一结点，交换当前root的左右子树
if(root.left != null && root.left.val != voyage[i+1]) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 交换完左右子树后，把当前root加入res返回列表
res.add(root.val);
}
i++;
// 前序遍历
dfs(root.left, voyage);
dfs(root.right, voyage);
}
}
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(N)$，递归栈+列表
993. 二叉树的堂兄弟节点
专题：二叉树其他 968. 监控二叉树在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。（每个结点的值都是0）
一、解题思路
本题为hard级别。
二、代码+复杂度复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：
979. 在二叉树中分配硬币
给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。(1<=N<=100，0<=node.val<=N)
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回
使每个结点上只有一枚硬币所需的移动次数。
每个结点的值最小为0，最大为N（结点个数），定义dfs函数返回值为“过载量”，其功能在于计算以node为顶点的子树需要多少硬币才平衡，正数表示我有多余，负数表示我需要别人给我硬币。
采用后序递归，从根结点开始，单次递归操作为：求出当前结点需要从左子树和右子树中拿出的金币数量（正数、负数、0），那么移动次数（把左右子树中多余的移到当前结点，或者从当前结点移到左右子树）就是从左右子树中拿走的金币绝对值。当前结点处理完成后，此时当前root的金币数量为 root.val + left + right，那返回值为返回当前结点只需保留一个金币时，需要拿走的金币数。
private int res;
public int distributeCoins(TreeNode root) {
res = 0;
dfs(root);
return res;
}
public int dfs(TreeNode root){
if(root == null) return 0;
// 需要从左子树中拿出的金币数量，可能为正数、负数、0
int left = dfs(root.left);
// 需要从右子树中拿出的金币数量，可能为正数、负数、0
int right = dfs(root.right);
// 移动次数就是从左右子树中拿走的金币绝对值
res += Math.abs(left) + Math.abs(right);
// 此时当前root的金币数量为 root.val + left + right，返回
// 只需保留一个金币时，需要拿走的金币数
return root.val + left + right - 1;
}
递归树如下图所示：
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$为为树中节点的数目。
- 空间复杂度：$O(H)$，其中$H$是树的高度。