树
二叉树的递归遍历
先确定递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证写出正确的递归算法！
- **确定递归函数的参数和返回值：**确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- **确定终止条件：**递归算法执行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- **确定单层递归的逻辑：**确定每一层递归需要处理的信息，此处也就是会重复调用自己来实现递归的过程。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
//前序遍历
preorder(root, result);
//中序遍历
inorder(root,result);
//后序遍历
postorder(root,result);
return result;
}
//前序遍历
public void preorder(TreeNode root,List<Integer> result) {
if(root == null) {
return;
}
result.add(root.val);
preorder(root.left,result);
preorder(root.right,result);
}
//中序遍历
public void inorder(TreeNode root,List<Integer> result) {
if(root == null) {
return;
}
inorder(root.left,result);
result.add(root.val);
inorder(root.right,result);
}
//后序遍历
public void postorder(TreeNode root,List<Integer> result) {
if(root == null) {
return;
}
postorder(root.left,result);
postorder(root.right,result);
result.add(root.val);
}
二叉树的迭代遍历
用栈实现前序、后序迭代遍历。前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子，这样在出栈时才能保证正确的中左右顺序。
前序遍历（迭代法）
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.pop();
result.add(temp.val);
if(temp.right != null) {
stack.push(temp.right);
}
if(temp.left != null) {
stack.push(temp.left);
}
}
return result;
}
后序遍历（迭代法）
前序遍历是中左右，后序遍历是左右中，所以只需调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后再反转result数组，输出的结果顺序就是左右中了，如下图：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.pop();
result.add(temp.val);
//此处代码与前序遍历相反 应先将左孩子入栈，右孩子后入栈。出栈顺序才会是中右左。
if(temp.left != null) {
stack.push(temp.left);
}
if(temp.right != null) {
stack.push(temp.right);
}
}
//将结果集进行反转即可得到左右中
Collections.reverse(result);
return result;
}
中序遍历（迭代法）
在使用迭代法写中序遍历时，需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
//不断将左孩子入栈
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else { //当左孩子为空时，便可出栈并将其记录
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
leetcode相关题目：
二叉树的层序遍历
实现层序遍历需要借助一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑。而栈先进后出，适合模拟深度优先遍历也就是递归的逻辑。使用队列实现二叉树广度优先遍历，动画如下：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
//迭代法————借助队列
if(root == null) return resList;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()) {
List<Integer> itemList = new ArrayList<>();
resList.add(itemList);
int len = que.size();
while(len > 0) { //每层的节点出队后都将其左右孩子依次入队，直到该层节点出队完毕，结束本轮循环
TreeNode tempNode = que.poll();
itemList.add(tempNode.val);
if(tempNode.left != null) que.offer(tempNode.left);
if(tempNode.right != null) que.offer(tempNode.right);
len--;
}
}
return resList;
}
//递归方式 checkFun01(root,0);
public void checkFun01(TreeNode root,int deep) {
if(root == null) return;
deep++;
if(resList.size() < deep) {
List<Integer> list = new ArrayList<>();
resList.add(list);
}
resList.get(deep - 1).add(root.val);
checkFun01(root.left,deep);
checkFun01(root.right,deep);
}
二叉树的相关类型题：
- 102.二叉树的层序遍历
- 107.二叉树的层次遍历II
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429.N叉树的层序遍历
- 515.在每个树行中找最大值
- 116.填充每个节点的下一个右侧节点指针
- 117.填充每个节点的下一个右侧节点指针II
- 104.二叉树的最大深度
- 111.二叉树的最小深度
翻转二叉树
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果
前序、后序遍历递归解法：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
swap(root); //前序解法
invertTree(root.left);
invertTree(root.right);
//swap(root); 后序解法只需将代码移至此处即可
/*
invertTree(root.left);
swap(root); //中序也可解题
invertTree(root.left); 此处依然要遍历左节点，否则会导致二次翻转。但这毕竟不是真正的中序递归遍历了。
*/
return root;
}
//交换左右孩子节点
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
层序遍历（队列）：
public TreeNode invertTree(TreeNode root) {
//层序遍历解法
if(root == null) {
return null;
}
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.offer(root);
while (!deque.isEmpty()) {
int size = deque.size();
while (size-- > 0) {
TreeNode node = deque.poll();
swap(node);
if (node.left != null) {deque.offer(node.left);}
if (node.right != null) {deque.offer(node.right);}
}
}
return root;
}
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
前序遍历（利用栈的迭代解法）：
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.pop(); //中
swap(node);
if(node.right) stack.push(node.right); //右
if(node.left) stack.push(node.left); //左
}
return root;
}
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
leetcode相关题目：
对称二叉树
本题遍历只能是“后序遍历”，因为要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个数的遍历顺序是右左中。
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return compare(root.left,root.right);
}
//递归法
public boolean compare(TreeNode left,TreeNode right) {
//各种判断对称二叉树的退出递归条件
if(left == null && right !=null) {
return false;
}
if(left != null && right == null) {
return false;
}
if(left.val != right.val) {
return false;
}
if(left == null && right == null) {
return true;
}
//if(left == null || right == null || left.val != right.val) return false; 前三个if可化简为此行代码
boolean compareOutside = compare(left.left,right.right);
boolean compareInside = compare(left.right,right.left);
return compareOutside && compareInside;
}
迭代法：
public boolean isSymmetric(TreeNode root) {
//迭代法 使用普通队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root.left);
queue.add(root.right);
while(!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if(left == null && right == null) {
continue;
}
if(left == null || right == null || left.val != right.val) {
return false;
}
queue.add(left.left);
queue.add(right.right);
queue.add(left.right);
queue.add(right.left);
}
//迭代法 使用双端队列
/*Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()) {
TreeNode left = deque.pollFirst();
TreeNode right = deque.pollLast();
if(left == null && right == null) {
continue;
}
if(left == null || right == null || left.val != right.val) {
return false;
}
deque.offerFirst(left.left);
deque.offerLast(right.right);
deque.offerFirst(left.right);
deque.offerLast(right.left);
}*/
return true;
}
//也可使用栈来解答此题，只需将队列换为栈即可，稍作改动。此处省略。
leetcode相关题目：
二叉树的最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。本题可以使用前序，也可以使用后序遍历，使用前序求的就是深度，使用后序求的是高度。而根节点的高度就是二叉树的最大深度。
public int maxDepth(TreeNode root) {
//递归法 后序遍历求最大深度
//return getDepth(root);
//前序遍历求最大深度
if(root == null) {
return 0;
}
lastGetDepth(root,1);
return result;
}
//后序递归
public int getDepth(TreeNode root) {
if(root == null) {
return 0;
}
int MaxLeft = getDepth(root.left);
int MaxRight = getDepth(root.right);
int depth = Math.max(MaxLeft,MaxRight) + 1;
return depth;
}
//前序递归
int result = 0;
public void lastGetDepth(TreeNode root,int depth) {
result = depth > result ? depth : result;
if(root.left == null && root.right == null) return;
if(root.left != null) lastGetDepth(root.left,depth + 1); //隐藏着回溯
if(root.right != null) lastGetDepth(root.right,depth + 1); //回溯
return;
}
使用迭代法的话，层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。在二叉树中，一层一层的来遍历二叉树，记录以下遍历的层数就是二叉树的深度，如图所示：
public int maxDepth(TreeNode root) {
//迭代法 层序遍历求最大深度
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0;
while(!queue.isEmpty()) {
int Length = queue.size();
count++;
while(Length > 0) {
TreeNode temp = queue.poll();
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
Length--;
}
}
return count;
}
n叉树的最大深度
依然可以提高递归法和迭代法来解决此问题，其思路和求解二叉树的最大深度是一样的。
public int maxDepth(Node root) {
//递归法
if(root == null) {
return 0;
}
int depth = 0;
if(root.children != null) {
for(Node child : root.children) {
depth = Math.max(depth,maxDepth(child));
}
}
return depth + 1;
}
public int maxDepth(Node root) {
//迭代法 层序遍历
if(root == null) {
return 0;
}
int depth = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int Length = queue.size();
depth++;
while(Length > 0) {
Node temp = queue.poll();
for(int i = 0; i < temp.children.size(); i++) {
queue.add(temp.children.get(i));
}
Length--;
}
}
return depth;
}
leetcode相关题目：
二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。遍历顺序上依然是后序遍历（因为要比较递归返回之后的结果），但在处理中间节点的逻辑上，最小深度有一个误区，如图：
public int minDepth(TreeNode root) {
return getDepth(root);
}
public int getDepth(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if(leftDepth == 0 && rightDepth != 0) {
return rightDepth + 1;
}
if(leftDepth != 0 && rightDepth == 0) {
return leftDepth + 1;
}
return Math.min(leftDepth,rightDepth) + 1;
}
迭代法：需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子为空则不是最低点。
public int minDepth(TreeNode root) {
//迭代法 层序遍历
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while(!queue.isEmpty()) {
int Length = queue.size();
depth++;
while(Length > 0) {
TreeNode temp = queue.poll();
if(temp.left == null && temp.right == null) return depth;
if(temp.left != null) {
queue.add(temp.left);
}
if(temp.right != null) {
queue.add(temp.right);
}
Length--;
}
}
return depth;
}
leetcode相关问题：
完全二叉树的节点个数
首先按照普通二叉树的逻辑求解，此题目的递归法和求二叉树的深度写法类似。
public int countNodes(TreeNode root) {
//递归法 和求深度的写法类似
if(root == null) {
return 0;
}
int leftNums = countNodes(root.left);
int rightNums = countNodes(root.right);
int count = leftNums + rightNums + 1;
return count;
}
迭代法：只需对层序遍历的模板做少量改动，统计节点数量即可。
public int countNodes(TreeNode root) {
//迭代法
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0;
while(!queue.isEmpty()) {
int Length = queue.size();
while(Length > 0) {
TreeNode temp = queue.poll();
count++;
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
Length--;
}
}
return count;
}
完全二叉树：
其只有两种情况，情况一：就是满二叉树。情况二：最后一层叶子节点没有满。
对于情况一，可以直接用2^树深度-1来计算，注意这里根节点深度为1。对于情况二，分别递归左孩子和右孩子，递归到某一深度时一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况一来计算。例图如下：
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树的节点数量）。
public int countNodes(TreeNode root) {
//利用完全二叉树的性质的解法 满二叉树的结点数为 2^depth - 1
if(root == null) {
return 0;
}
TreeNode left = root.left;
TreeNode right = root.right;
int leftHeight = 0;
int rightHeight = 0;
//求左子树的高度
while(left) {
left = left.left;
leftHeight++;
}
//求右子树的高度
while(right) {
right = right.right;
rightHeight++;
}
if(leftHeight == rightHeight) {
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
//等价于上面的代码
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {// 左子树是满二叉树
// 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
return (1 << leftDepth) + countNodes(root.right);
} else {// 右子树是满二叉树
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
leetcode相关问题：
平衡二叉树
一棵高度平衡的二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
//递归法需掌握
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1 ? false : true;
}
public int getHeight(TreeNode node) {
if(node == null) {
return 0;
}
int leftHeight = getHeight(node.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(node.right);
if(rightHeight == -1) return -1;
return Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight,rightHeight) + 1;
}
二叉树的所有路径
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。因为需要把路径记录下来，需要回溯来回退一个节点，以此进入另一个路径。
public List<String> binaryTreePaths(TreeNode root) {
//递归法
List<String> result = new ArrayList<>();
if(root == null) {
return result;
}
List<Integer> paths = new ArrayList<>();
traversal(root,paths,result);
return result;
}
public void traversal(TreeNode root,List<Integer> paths,List<String> result) {
paths.add(root.val);
//判断是否为叶子节点，如果是的话将沿途的路径记录在result中
if(root.left == null && root.right == null) {
StringBuilder str = new StringBuilder();
for(int i = 0; i < paths.size() - 1; i++) {
str.append(paths.get(i)).append("->");
}
str.append(paths.get(paths.size() - 1));
result.add(str.toString());
return;
}
//如果不是非叶子节点，则继续遍历，直到找到叶子节点为止，退出递归后需进行回溯操作
if(root.left != null) {
traversal(root.left,paths,result);
paths.remove(paths.size() - 1); //回溯
}
if(root.right != null) {
traversal(root.right,paths,result);
paths.remove(paths.size() - 1); //回溯
}
}
迭代法（借助栈）
public List<String> binaryTreePaths(TreeNode root) {
//迭代法
List<String> result = new ArrayList<>();
if (root == null)
return result;
Stack<Object> stack = new Stack<>();
// 节点和路径同时入栈
stack.push(root);
stack.push(root.val + "");
while (!stack.isEmpty()) {
// 节点和路径同时出栈
String path = (String) stack.pop();
TreeNode node = (TreeNode) stack.pop();
// 若找到叶子节点
if (node.left == null && node.right == null) {
result.add(path);
}
//右子节点不为空
if (node.right != null) {
stack.push(node.right);
stack.push(path + "->" + node.right.val);
}
//左子节点不为空
if (node.left != null) {
stack.push(node.left);
stack.push(path + "->" + node.left.val);
}
}
return result;
}
左叶子之和
如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子。所以判断当前节点是不是左叶子是无法判断的，必须通过节点的父节点来判断其左孩子是不是左叶子。如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到一个左叶子。
//递归法
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left);
int rightValue = sumOfLeftLeaves(root.right);
int midValue = 0;
if(root.left != null && root.left.left == null && root.left.right == null) {
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue;
return sum;
}
迭代法（栈）
public int sumOfLeftLeaves(TreeNode root) {
//迭代法
if(root == null) return 0;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int result = 0;
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
//重点代码
if(node.left != null && node.left.left == null && node.left.right == null) {
result += node.left.val;
}
if(node.right != null) stack.push(node.right);
if(node.left != null) stack.push(node.left);
}
return result;
}
//也可用层序遍历迭代 在原模板的基础上修改以下几行代码即可
/*if (node.left != null) { // 左节点不为空
queue.offer(node.left);
if (node.left.left == null && node.left.right == null){ // 左叶子节点
sum += node.left.val;
}
}*/
找树左下角的值
本题要遍历整个树找到最深的叶子节点，需要遍历整棵树，所以递归函数没有返回值。当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。当找到最大深度的时候，递归的过程依然要使用回溯。
private int maxDepth = -1;
private int leftValue = 0;
public int findBottomLeftValue(TreeNode root) {
leftValue = root.val;
findLeftValue(root,0);
return leftValue;
}
public void findLeftValue(TreeNode root,int depth) {
if(root == null) return;
if(root.left == null && root.right == null) {
if(depth > maxDepth) {
maxDepth = depth;
leftValue = root.val;
}
return;
}
if(root.left != null) {
/*depth++; //深度加一
findLeftValue(root.left,depth);
depth--; */ //回溯
//以上三行代码可简化为一行代码 递归中隐藏着回溯
findLeftValue(root.left,depth + 1);
}
if(root.right != null) {
/*depth++;
findLeftValue(root.right,depth);
depth--;*/
//以上三行代码可简化为一行代码 递归中隐藏着回溯
findLeftValue(root.right,depth + 1);
}
}
迭代法：
public int findBottomLeftValue(TreeNode root) {
//迭代法 层序遍历
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int result = 0;
while(!queue.isEmpty()) {
int length = queue.size();
for(int i = 0; i < length; i++) {
TreeNode node = queue.poll();
if(i == 0) result = node.val;
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
return result;
}
路径总和
递归函数什么时候需要返回值？
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径就要及时返回。
本题可以让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。如果最后count == 0，同时节点为叶子节点的话，说明找到了目标和。如果遍历到了叶子结点，count不为0，就是没找到，此时需要回溯。
public boolean hasPathSum(TreeNode root, int targetSum) {
//递归法
if(root == null) return false;
return traversal(root,targetSum - root.val);
}
public boolean traversal(TreeNode root, int count) {
if(root.left == null && root.right == null && count == 0) return true; //为叶子节点且计数为0
if(root.left == null && root.right == null) return false; //遇到叶子节点但计数不为0，直接返回
if(root.left != null) {
if(traversal(root.left,count - root.left.val)) return true; //此代码中隐藏着回溯
}
if(root.right != null) {
if(traversal(root.right,count - root.right.val)) return true; //此代码中隐藏着回溯
}
return false;
}
迭代法：（双栈）
public boolean hasPathSum(TreeNode root, int targetSum) {
//迭代法 （栈）前序遍历
if(root == null) return false;
Stack<TreeNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
stack1.push(root);
stack2.push(root.val);
while(!stack1.isEmpty()) {
int length = stack1.size();
TreeNode node = stack1.pop();
int count = stack2.pop();
if(node.left == null && node.right == null && count == targetSum) return true;
if(node.right != null) {
stack1.push(node.right);
stack2.push(count + node.right.val);
}
if(node.left != null) {
stack1.push(node.left);
stack2.push(count + node.left.val);
}
}
return false;
}
路径总和II要遍历整个树，找到所有路径，所以递归函数不要返回值！
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root == null) return result;
traversal(root,targetSum - root.val);
return result;
}
public void traversal(TreeNode root,int count) {
path.add(root.val);
if(root.left == null && root.right == null && count == 0) {
result.add(new ArrayList<>(path));
return;
}
if(root.left == null && root.right == null) return;
if(root.left != null) {
traversal(root.left,count - root.left.val);
path.remove(path.size() - 1);
}
if(root.right != null) {
traversal(root.right,count - root.right.val);
path.remove(path.size() - 1);
}
}
从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树（树中没有重复元素）。以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
切割中序数组，找到后序数组的最后一个元素在中序数组的位置，然后进行切割。后序数组的最后一个元素忽略掉，因为是切割点。中序数组被切割点切成了左中序数组和右中序数组，那么后序数组就可以按照左右中序数组的大小来切割，切割成左后序数组和右后序数组。坚持左闭右开的原则！
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree1(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode buildTree1(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight) {
//没有元素了 这里采用的是左闭右开原则
if(inRight - inLeft < 1) {//相当于是inRight==inLeft 因为右开，所以inRight是取不到值的，所以此时返回null
return null;
}
//后序数组postorder里最后一个元素即为根节点
int rootVal = postorder[postRight - 1];
TreeNode root = new TreeNode(rootVal);
//只有一个元素了 此处同理
if(inRight - inLeft == 1) {
return root;
}
int rootIndex = 0;
//根据根节点的值找到该值在中序数组inorder里的位置
for(int i = inLeft; i < inRight; i++) {
if(inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
//切割中序数组
//左中序区间，左闭右开[leftInorderBegin,leftInorderEnd]
int leftInorderBegin = inLeft;
int leftInorderEnd = rootIndex;
//右中序区间，左闭右开[rightInorderBegin,rightInorderEnd]
int rightInorderBegin = rootIndex + 1;
int rightInorderEnd = inRight;
//切割后序数组
//左后序区间，左闭右开[leftPostorderBegin,leftPostorderEnd]
int leftPostorderBegin = postLeft;
int leftPostorderEnd = postLeft + rootIndex - inLeft;
//右后序区间，左闭右开[rightPostorderBegin,rightPostorderEnd]
int rightPostorderBegin = postLeft + rootIndex - inLeft;
int rightPostorderEnd = postRight - 1; //排除最后一个元素
root.left = buildTree1(inorder,leftInorderBegin,leftInorderEnd,postorder,leftPostorderBegin,leftPostorderEnd);
root.right = buildTree1(inorder,rightInorderBegin,rightInorderEnd,postorder,rightPostorderBegin,rightPostorderEnd);
return root;
}
从中序与前序遍历序列构造二叉树
与上面的同理，只不过此时切割点变成了前序遍历的第一个节点。
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder.length == 0 || preorder.length == 0) return null;
//参数坚持左闭右开的原则
return traversal(inorder,0,inorder.length,preorder,0,preorder.length);
}
public TreeNode traversal(int[] inorder,int inorderBegin,int inorderEnd,int[] preorder,int preorderBegin,int preorderEnd) {
//没有元素了
if(preorderEnd - preorderBegin < 1) return null;
//前序数组里第一个元素即为根节点
int rootValue = preorder[preorderBegin]; //注意用preorderBegin 不要用0
TreeNode root = new TreeNode(rootValue);
if(preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if(inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
//切割前序数组
//前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + delimiterIndex - inorderBegin;
int rightPreorderEnd = preorderEnd;
root.left = traversal(inorder,leftInorderBegin,leftInorderEnd,preorder,leftPreorderBegin,leftPreorderEnd);
root.right = traversal(inorder,rightInorderBegin,rightInorderEnd,preorder,rightPreorderBegin,rightPreorderEnd);
return root;
}
最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树
- 右子树是通过数组中最大值右边部分构造出的最大二叉树
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。每次分隔数组不采用定义新数组的形式，而是通过下标索引直接在原数组上操作。坚持左闭右开原则。
public TreeNode constructMaximumBinaryTree(int[] nums) {
return traversal(nums,0,nums.length); //坚持左闭右开
}
public TreeNode traversal(int[] nums,int leftIndex,int rightIndex) {
if(leftIndex >= rightIndex) return null;//左闭右开
int maxIndex = leftIndex; //最大值所在位置
int maxVal = nums[leftIndex]; //最大值
for(int i = leftIndex + 1; i < rightIndex; i++) {
if(maxVal < nums[i]) {
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);//先构造中间节点，然后构造左右子树
//根据maxIndex划左右子树
root.left = traversal(nums,leftIndex,maxIndex);//左闭右开
root.right = traversal(nums,maxIndex + 1,rightIndex);
return root;
}
合并二叉树
合并的规则是如果两个节点重叠，那么将两节点相加的值作为节点合并后的新值，否则将不为null的节点直接作为新二叉树的节点。
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//递归法
if(root1 == null) {
return root2;
}
if(root2 == null) {
return root1;
}
//重新定义新的节点，不修改原有两个树的结构
TreeNode root = new TreeNode();
root.val = root1.val + root2.val;
root.left = mergeTrees(root1.left,root2.left);
root.right = mergeTrees(root1.right,root2.right);
return root;
}
迭代法：使用双队列模拟
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//使用队列迭代 也可使用栈迭代，与队列迭代类似
if(root1 == null) return root2;
if(root2 == null) return root1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root1);
queue.add(root2);
while(!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
//此时两节点一定不为空 修改的是原root1的树
node1.val = node1.val + node2.val;
//如果是两棵树的左子树都不为空，加入队列
if(node1.left != null && node2.left != null) {
queue.add(node1.left);
queue.add(node2.left);
}
//如果是两棵树的右子树都不为空，加入队列
if(node1.right != null && node2.right != null) {
queue.add(node1.right);
queue.add(node2.right);
}
//如果是node1的左节点为空，则直接赋值
if(node1.left == null && node2.left != null) {
node1.left = node2.left;
}
//如果是node1的右节点为空，则直接赋值
if(node1.right == null && node2.right != null) {
node1.right = node2.right;
}
}
return root1;
}
二叉搜索树中的搜索
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为二叉搜索树
public TreeNode searchBST(TreeNode root, int val) {
//递归 利用二叉搜索树的特点
if(root == null || root.val == val) return root;
if(root.val > val) {
//此处添加了return 因为搜索到目标节点之后就要立即返回了，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树。
return searchBST(root.left,val);
}
if(root.val < val) {
return searchBST(root.right,val);
}
return null;
}
迭代法：
public TreeNode searchBST(TreeNode root, int val) {
// 迭代，利用二叉搜索树特点，优化，可以不需要栈
while(root != null) {
if(root.val > val) {
root = root.left;
}else if(root.val < val) {
root = root.right;
}else {
return root;
}
}
return null;
}
验证二叉搜索树
在中序遍历下，输出的二叉搜索树节点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增序列。
-
陷阱一：不能单纯的比较左节点小于中间节点，右节点大于中间节点。要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点。
-
陷阱2：样例中最小节点可能是int的最小值，初始化最小值时应注意！应尽量避免初始化最小值。
Long max = Long.MIN_VALUE; //初始化最小值
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
boolean left = isValidBST(root.left); //左
if(root.val > max) {
max = (long)root.val;
}else { //中
return false;
}
boolean right = isValidBST(root.right); //右
return left && right;
}
//避免初始化最小值的方式
TreeNode pre = NULL; // 用来记录前一个节点
boolean isValidBST(TreeNode root) {
if (root == NULL) return true;
boolean left = isValidBST(root.left);
if (pre != NULL && pre.val >= root.val) return false;
pre = root; // 记录前一个节点
boolean right = isValidBST(root->right);
return left && right;
}
迭代法：
public boolean isValidBST(TreeNode root) {
//迭代法 中序遍历
if(root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if(pre != null && cur.val <= pre.val) {
return false;
}
pre = cur;
cur = cur.right;
}
}
return true;
}
二叉搜索树的最小绝对差
给定一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的。要掌握使用双指针法，记录前后两个指针。
TreeNode pre; //记录上一个节点的指针
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) { //递归法
traversal(root);
return result;
}
public void traversal(TreeNode root) {
if(root == null) return;
traversal(root.left); //左
if(pre != null) {
result = Math.min(result,root.val - pre.val);
}
pre = root; //此行代码为记录前一个节点
traversal(root.right); //右
}
迭代法：
TreeNode pre; //记录上一个节点的指针
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
//迭代法
if(root == null) return 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if(pre != null) {
result = Math.min(result,cur.val - pre.val);
}
pre = cur;
cur = cur.right;
}
}
return result;
}
二叉搜索树的众数
给定一个有相同值的二叉搜索树，找出其中的所有众数（出现频率最高的元素）。
ArrayList<Integer> resList; //结果集
int maxCount; //最大频率
int count; //统计频率
TreeNode pre; //指向前一个节点 */
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[] result = new int[resList.size()];
for(int i = 0; i < resList.size(); i++) {
result[i] = resList.get(i);
}
return result;
}
public void findMode1(TreeNode root) {
if(root == null) return;
findMode1(root.left); //左
if(pre == null || root.val != pre.val) {
count = 1;
}else {
count++;
}
if(count > maxCount) {
resList.clear();
resList.add(root.val);
maxCount = count;
}else if(count == maxCount){
resList.add(root.val);
}
pre = root;
findMode1(root.right); //右
}
按照正常的逻辑应该是先遍历一遍数组，找出最大频率maxCount，然后再重新遍历一遍数组，把出现频率为maxCount的元素放进集合，因为众数可能有多个。
此处有个巧妙的技巧，它每次都将频率为count的元素放进结果集中，当遇到更大的count时，将原结果集清空，将此元素放入结果集中并更新maxCount，，如果count与maxCount相同，则继续将元素加入结果集中，这样就只需一次遍历就可以满足题意了。
迭代法：（只需将中序遍历的迭代模板加上上面的逻辑即可）
public int[] findMode(TreeNode root) {
//迭代法
List<Integer> result = new ArrayList<>();
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
int count = 0;
int maxCount = 0;
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if(pre == null || cur.val != pre.val) {
count = 1;
}else {
count++;
}
if(count > maxCount) {
result.clear();
result.add(cur.val);
maxCount = count;
}else if(count == maxCount) {
result.add(cur.val);
}
pre = cur;
cur = cur.right;
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
连续的两道题都使用了双指针法，一个指向当前节点，一个指向当前节点的前一个节点。需总结掌握此方法。
二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。（一个节点也可以是它自己的祖先）
如果递归函数有返回值，如何区分要搜索一条边，还是搜索整棵树呢？
搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整棵树的写法：
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回。如果搜索整棵树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
//后序遍历
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null && right == null) {
return null;
}else if(left != null && right == null){
return left;
}else if(left == null && right != null) {
return right;
}else {
return root;
}
}
二叉搜索树的最近公共祖先
给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。因为二叉搜索树是有序的，所以只要从上到下遍历，cur节点是数值在[p,q]区间中则说明该节点cur就是最近公共祖先了。
可以看出直接按照指定的方向，就可以找到节点4，为最近公共祖先，而且不需要遍历整棵树，找到结果直接返回！
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归法
return traversal(root,p,q);
}
public TreeNode traversal(TreeNode cur,TreeNode p, TreeNode q) {
if(cur == null) return null;
if(cur.val > p.val && cur.val > q.val) { //左
TreeNode left = traversal(cur.left,p,q);
if(left != null) {
return left;
}
}
if(cur.val < p.val && cur.val < q.val) { //右
TreeNode right = traversal(cur.right,p,q);
if(right != null) {
return right;
}
}
return cur;
}
迭代法：利用其有序性
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//迭代法 利用其有序性
while(root != null) {
if(root.val > p.val && root.val > q.val) {
root = root.left;
}else if(root.val < p.val && root.val < q.val) {
root = root.right;
}else {
return root;
}
}
return null;
}
二叉搜索树中的插入操作
给定一个二叉搜索树的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证新值和原始二叉搜索树中的任意节点值都不同。
其实可以不考虑题目中所说的改变树的结构的插入方式。只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
public TreeNode insertIntoBST(TreeNode root, int val) {
//递归法 带返回值的解法
if(root == null) {
TreeNode node = new TreeNode(val);
return node;
}
if(root.val > val) {
root.left = insertIntoBST(root.left,val);
}
if(root.val < val) {
root.right = insertIntoBST(root.right,val);
}
return root;
}
TreeNode pre = new TreeNode(0);
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) {
root = new TreeNode(val);
}
tarversal(root,val);
return root;
}
//不带返回值的递归调用 需要记录上一个节点pre，遇到空节点了，就让pre左孩子或者右孩子指向新插入的节点，然后结束递归。
public void traversal(TreeNode cur,int val) {
if(cur == null) {
TreeNode node = new TreeNode(val);
if(pre.val > node.val) {
pre.left = node;
}else {
pre.right = node;
}
return;
}
pre = cur;
if(cur.val > val) traversal(cur.left,val);
if(cur.val < val) traversal(cur.right,val);
}
迭代法：
TreeNode pre = new TreeNode(0);
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) {
root = new TreeNode(val);
return root;
}
TreeNode cur = root;
TreeNode pre = null;
while(cur != null) {
pre = cur;
if(cur.val > val) {
cur = cur.left;
}else {
cur = cur.right;
}
}
TreeNode node = new TreeNode(val);
if(pre.val > node.val) {
pre.left = node;
}else {
pre.right = node;
}
return root;
删除二叉搜索树中的节点
给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树的根节点的引用。
- 没找到待删除的节点，遍历到空结点直接返回了
- 找到删除的节点：
- 左右孩子都为空（叶子节点），直接删除节点，返回null为根节点
- 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
if(root.val == key) {
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
if(root.left == null && root.right == null) {
return null;
}
// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
else if(root.left == null) {
return root.right;
}
// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
else if(root.right == null) {
return root.left;
}
// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
else {
TreeNode cur = root.right;
while(cur.left != null) { //找右子树最左边的节点
cur = cur.left;
}
cur.left = root.left;
root = root.right;
}
}
if(root.val > key) root.left = deleteNode(root.left,key);
if(root.val < key) root.right = deleteNode(root.right,key);
return root;
}
迭代法：
public TreeNode deleteNode(TreeNode root, int key) {
//迭代法
if(root == null) return root;
TreeNode cur = root;
TreeNode pre = null; //记录cur的父节点，用来删除cur
while(cur != null) { //找到待删除的节点及其父节点
if(cur.val == key) break;
pre = cur;
if(cur.val > key) {
cur = cur.left;
}else {
cur = cur.right;
}
}
if(pre == null) { //如果搜索树只有头节点
return deleteOneNode(cur,key);
}
if(pre.left != null && pre.left.val == key) {
pre.left = deleteOneNode(cur,key);
}
if(pre.right != null && pre.right.val == key) {
pre.right = deleteOneNode(cur,key);
}
return root;
}
//重点逻辑 无论递归和迭代 都需采用的代码
public TreeNode deleteOneNode(TreeNode root,int key) {
if(root == null) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
if(root.val == key) {
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
if(root.left == null && root.right == null) {
return null;
}
// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
else if(root.left == null) {
return root.right;
}
// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
else if(root.right == null) {
return root.left;
}
// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
else {
TreeNode cur = root.right;
while(cur.left != null) { //找右子树最左边的节点
cur = cur.left;
}
cur.left = root.left;
root = root.right;
}
}
return root;
}
修剪二叉搜索树
给定一个二叉搜索树，同时给定最小边界L和最大边界R。通过修剪二叉搜索树，使得所有节点的值在[L,R]中（R>=L）。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
public TreeNode trimBST(TreeNode root, int low, int high) {
//递归法
if(root == null) {
return null;
}
if(root.val < low) {
TreeNode right = trimBST(root.right,low,high);
return right;
}
if(root.val > high) {
TreeNode left = trimBST(root.left,low,high);
return left;
}
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
迭代法：
public TreeNode trimBST1(TreeNode root, int low, int high) {
if(root == null) return null;
// 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
while(root != null && (root.val < low || root.val > high)) {
if(root.val < low) root = root.right; //小于往右走
else root = root.left; //大于往左走
}
TreeNode cur = root;
// 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
while(cur != null) {
while(cur.left != null && cur.left.val < low) {
cur.left = cur.left.right;
}
cur = cur.left;
}
cur = root;
// 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
while(cur != null) {
while(cur.right != null && cur.right.val > high) {
cur.right = cur.right.left;
}
cur = cur.right;
}
return root;
}
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡的二叉搜索树。
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = traversal(nums,0,nums.length - 1); //遵循左闭右闭原则
return root
}
public TreeNode traversal(int[] nums,int left,int right) {
if(left > right) return null;
int middle = left + ((right - left) / 2);
TreeNode root = new TreeNode(nums[middle]);
root.left = traversal(nums,left,middle - 1);
root.right = traversal(nums,middle + 1,right);
return root;
}
迭代法：
public TreeNode sortedArrayToBST(int[] nums) {
//迭代法 采用队列模拟
if(nums.length == 0) return null;
//根节点初始化
TreeNode root = new TreeNode(-1);
Queue<TreeNode> nodeQueue = new LinkedList<>(); //放遍历的节点
Queue<Integer> leftQueue = new LinkedList<>(); //保存左区间下标
Queue<Integer> rightQueue = new LinkedList<>(); //保存右区间下标
//根节点入队列
nodeQueue.add(root);
leftQueue.add(0);
rightQueue.add(nums.length - 1);
while(!nodeQueue.isEmpty()) {
TreeNode currNode = nodeQueue.poll();
int left = leftQueue.poll();
int right = rightQueue.poll();
int mid = left + ((right - left) / 2);
//将mid对应的中间元素给中间节点
currNode.val = nums[mid];
//处理左区间
if(left <= mid - 1) {
currNode.left = new TreeNode(-1);
nodeQueue.add(currNode.left);
leftQueue.add(left);
rightQueue.add(mid - 1);
}
//处理右区间
if(right >= mid + 1) {
currNode.right = new TreeNode(-1);
nodeQueue.add(currNode.right);
leftQueue.add(mid + 1);
rightQueue.add(right);
}
}
return root;
}
有序链表转换二叉搜索树
给定一个单链表的头结点head，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉搜索树是指一个二叉树每个节点的左右两个子树的高度差不超过1。
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
根据中位数的性质，链表中小于中位数的元素个数与大于中位数的元素个数要么相等，要么相差1。此时小于中位数的元素组成了左子树，大于中位数的元素组成了右子树，它们分别对应着有序链表中连续的一段。在这之后使用分治的思想，继续递归地对左右子树进行构造，找出对应的中位数作为根节点，以此类推。
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head,null);
}
public TreeNode buildTree(ListNode left, ListNode right) {
if(left == right) return null;
ListNode mid = getMedian(left,right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left,mid);
root.right = buildTree(mid.next,right);
return root;
}
public ListNode getMedian(ListNode left,ListNode right) {
ListNode fast = left;
ListNode slow = left;
while(fast != right && fast.next != right) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
把二叉搜索树转换为累加树
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树，使每个节点node的新值等于原树中大于或等于node.val的值之和。
int pre = 0;
public TreeNode convertBST(TreeNode root) {
traversal(root);
return root;
}
public void traversal(TreeNode cur) {
if(cur == null) {
return;
}
traversal(cur.right);
cur.val += pre;
pre = cur.val;
traversal(cur.left);
}
迭代法：
int pre = 0;
public TreeNode convertBST(TreeNode root) {
//迭代法
if(root == null) return root;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.right;
}else {
cur = stack.pop();
cur.val += pre;
pre = cur.val;
cur = cur.left;
}
}
return root;
}
补充习题
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
二叉搜索树的中序遍历为递增序列。
- 排序链表：节点应从小到大排序，因此应使用中序遍历从小到大访问树的节点。
- 在构建相邻节点的引用关系时，设前驱节点pre和当前节点cur，不仅应构建pre.right = cur，也应构建cur.left = pre;
- 循环链表：设链表头结点head和尾节点tail，则应构建head.left = tail和tail.right = head;
Node pre = null;
Node head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
public void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，如果是则返回true，否则返回false。假设输入的数组的任意两个数字都不相同。
5
/ \
2 6
/ \
1 3
输入: [1,6,3,2,5]
输出: false
输入: [1,3,2,6,5]
输出: true
解题思路：
- 后序遍历定义：【左子树|右子树|根节点】，即遍历顺序为“左、右、根”。
- 二叉搜索树定义：左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。
!
递归分治：根据二叉搜索树的定义，可以通过递归，判断所有子树的正确性（即其后序遍历是否满足二叉搜索树的定义），若所有子树都正确，则此序列为二叉搜索树的后序遍历。
- 终止条件：当i >= j，说明此子树节点数量 <= 1，无需判别正确性，因此直接返回true；
- 递推工作：
- 划分左右子树：遍历后序遍历的[i,j]区间元素，寻找第一个大于根节点的节点，索引记为m。此时，可划分出左子树区间[i,m - 1]、右子树区间[m,j - 1]、根节点索引为j。
- 判断是否为二叉搜索树：
- 左子树[i,m-1]内的所有节点都应<postorder[j]。而第1“划分左右子树”步骤已经保证左子树区间的正确性，因此只需要判断右子树区间即可。
- 右子树区间[m,j-1]内的所有节点都应>postorder[j]。实现方式为遍历，当遇到<=postorder[j]的结点则跳出；可通过p=j判断是否为二叉搜索树。
- 返回值：所有子树都需正确才可判定正确，因此使用与逻辑符&&连接。
-
p==j ： 判断 此树 是否正确。
-
recur(i,m−1) ： 判断 此树的左子树 是否正确。
-
recur(m,j−1) ： 判断 此树的右子树 是否正确。
-
public boolean verifyPostorder(int[] postorder) {
return recur(postorder,0,postorder.length - 1);
}
public boolean recur(int[] postorder,int i, int j) {
if(i >= j) return true;
int temp = i;
while(postorder[temp] < postorder[j]) temp++;
int right = temp;
while(postorder[temp] > postorder[j]) temp++;
return temp == j && recur(postorder,i,right - 1) && recur(postorder,right,j - 1);
}
搜索二维矩阵II
编写一个高效的算法来搜索m×n矩阵matrix中的一个目标值target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列
- 每列的元素从上到下升序排列
可以将二维矩阵抽象成以右上角为根的BST：
那么可以从根(右上角)开始搜索，如果当前的结点不等于目标值，可以按照树的搜索顺序进行：
- 当前节点大于目标值，搜索当前节点的左子树，也就是当前矩阵位置的左方格子，即c--
- 当前节点小于目标值，搜索当前节点的右子树，也就是当前矩阵位置的下方格子，即r++
public boolean searchMatrix(int[][] matrix, int target) {
//抽象BST解法
int m = matrix.length;
int n = matrix[0].length;
int r = 0, c = n - 1;
while(r < m && c >= 0) {
if(matrix[r][c] < target) r++;
else if(matrix[r][c] > target) c--;
else return true;
}
return false;
}
两数之和IV - 输入BST
给定一个二叉搜索树root和一个目标结果k，如果BST中存在两个元素且它们的和等于给定的目标结果，则返回true。
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
//深度优先搜索 + 哈希表
/*if(root == null) return false;
if(set.contains(k - root.val)) return true;
set.add(root.val);
return findTarget(root.left,k) || findTarget(root.right,k);*/
//广度优先搜索 + 哈希表
/*Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int length = queue.size();
while(length > 0) {
TreeNode node = queue.poll();
if(set.contains(k - node.val)) return true;
set.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
length--;
}
}
return false;*/
//深度优先搜索 + 中序遍历 + 双指针
/*List<Integer> list = new ArrayList<>();
traversal(root,list);
int left = 0;
int right = list.size() - 1;
while(left < right) {
if(list.get(left) + list.get(right) > k) right--;
else if(list.get(left) + list.get(right) < k) left++;
else return true;
}
return false;*/
//迭代法 + 中序遍历 + 双指针
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
int left = 0;
int right = list.size() - 1;
while(left < right) {
if(list.get(left) + list.get(right) > k) right--;
else if(list.get(left) + list.get(right) < k) left++;
else return true;
}
return false;
}
/*public void traversal(TreeNode root,List<Integer> list) {
if(root == null) return;
traversal(root.left,list);
list.add(root.val);
traversal(root.right,list);
}*/
两棵二叉搜索树中的所有元素
给你root1和root2这两棵二叉搜索树。请你返回一个列表，其中包含两棵树中的所有整数并按升序排序。
输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]
利用BST中序遍历的有序性质，可以先对两棵树进行中序遍历，从而将树的结构转换为线性结构。将两个有序序列合并成一个有序序列则是利用了经典的归并排序。
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
inorder(root1,list1);
inorder(root2,list2);
List<Integer> merged = new ArrayList<Integer>();
int p1 = 0, p2 = 0;
while(true) {
if(p1 == list1.size()) {
merged.addAll(list2.subList(p2,list2.size()));
break;
}
if(p2 == list2.size()) {
merged.addAll(list1.subList(p1,list1.size()));
break;
}
if(list1.get(p1) < list2.get(p2)) {
merged.add(list1.get(p1++));
}
else {
merged.add(list2.get(p2++));
}
}
return merged;
}
public void inorder(TreeNode root,List<Integer> res) {
if(root == null) return;
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
恢复二叉搜索树
给你二叉搜索树的根节点root，该树中恰好两个节点的值被错误地交换。请在不改变结构的情况下，恢复这棵树。
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
如果在一个递增的序列中交换两个值会造成什么影响。假设有一个递增序列a=[1,2,3,4,5,6,7]。交换两个不相邻的数字，例如2和6，原序列变成了[1,6,3,4,5,2,7]，那么显然序列中有两个位置不满足ai < ai+1，在这个序列中体现为6>3,5>2，因此只要找到这两个位置，即可找到被错误交换的两个节点。如果交换两个相邻的数字，此时交换后的序列只有一个位置不满足ai < ai+1。因此整个值序列中不满足条件的位置或者有两个，或者有一个。
- 找到二叉搜索树中序遍历得到值序列的不满足条件的位置。
- 如果有两个，记为i和j，那么对应被错误交换的节点即为ai对应的节点和aj+1对应的节点，分别记为x和y。
- 如果有一个，记为i，那么对应被错误交换的节点即为ai对应的节点和ai+1对应的节点，分别记为x和y。
- 交换x和y两个节点即可。
开辟一个新数组nums来记录中序遍历得到的值序列，然后线序遍历找到两个位置i和j，并重新遍历原二叉搜索树修改对应节点的值完成修复。
隐式中序遍历
由于只关心中序遍历的值序列中每个相邻的位置的大小关系是否满足条件，且错误交换后最多两个位置不满足条件，因此在中序遍历的过程只需要维护当前中序遍历到的最后一个节点pre，然后再遍历到下一个节点的时候，看两个节点的值是否满足前者小于后者即可，如果不满足说明找到了一个交换的节点，且在找到两次以后就可以终止遍历。
public void recoverTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
TreeNode cur = root;
TreeNode x = null, y = null;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if(pre != null && pre.val > cur.val) {
y = cur;
if(x == null) {
x = pre;
}else {
break;
}
}
pre = cur;
cur = cur.right;
}
}
swap(x,y);
}
public void swap(TreeNode x, TreeNode y) {
int temp = x.val;
x.val = y.val;
y.val = temp;
}
后继者
设计一个算法，找出二叉搜索树中指定节点的下一个节点（也即中序后继）如果指定节点没有对应的下一个节点，则返回null。
输入: root = [2,1,3], p = 1
2
/ \
1 3
输出: 2
输入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
输出: null
中序遍历：由于只需要找到节点p的后继节点，因此不需要维护完整的中序遍历，只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。如果上一个访问的节点是p，则当前访问的节点即为p的后继节点。如果节点p是最后被访问的节点，则不存在节点p的后继节点，返回null。
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
if(pre == p) {
return cur;
}
pre = cur;
cur = cur.right;
}
}
return null;
}
利用二叉搜索树的性质：
二叉搜索树的一个性质是中序遍历序列单调递增，因此二叉搜索树中的节点p的后继节点满足以下条件：
- 后继节点的节点值大于p的节点值；
- 后继节点是节点值大于p的节点值的所有节点中节点值最小的一个节点。
如果节点p的右子树不为空，则节点p的后继节点在其右子树中，在其右子树中定位到最左边的节点，即为节点p的后继节点。
如果节点p的右子树为空，则需要从根节点开始遍历寻找节点p的祖先节点。将答案初始化为null。用node表示遍历到的节点值，初始时node = root。每次比较node的节点值和p的节点值，执行相应操作：
- 如果node的节点值大于p的节点值，则p的后继节点可能是node或者在node的左子树中，因此用node更新答案，并将node移动到其左子节点继续遍历；
- 如果node的节点值小于或等于p的节点值，则p的后继节点可能在node的右子树中，因此将node移动到其右子节点继续遍历。
由于在遍历过程中，当且仅当node的节点值大于p的节点值的情况下，才会用node更新答案，因此当节点p有后继节点时一定可以找到后继节点，当节点p没有后继节点时答案一定为null。
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
if (p.right != null) {
successor = p.right;
while (successor.left != null) {
successor = successor.left;
}
return successor;
}
TreeNode node = root;
while (node != null) {
if (node.val > p.val) {
successor = node;
node = node.left;
} else {
node = node.right;
}
}
return successor;
}
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）B是A的子结构，即A中出现和B相同的结构和节点值。
helper()函数：
- 终止条件：
- 当节点B为空：说明树B已匹配完成，因此返回true；
- 当节点A为空：说明已经越过树A叶子节点，即匹配失败，返回false；
- 当节点A和B的值不同：说明匹配失败，返回false；
- 返回值：
- 判断A和B的左子节点是否相等，即helper(A.left,B.left);
- 判断A和B的右子节点是否相等，即helper(A.right,B.right);
isSubStructure(A,B)函数：
- 特例处理：当树A为空或树B为空时，直接返回false；
- 返回值：若树B是树A的子结构，则必满足以下三种情况之一，因此用||连接
- 以节点A为根节点的子树包含树B，对应helper(A,B)；
- 树B是树A左子树的子结构，对应isSubStructure(A.left,B);
- 树B是树A右子树的子结构，对应isSubStructure(A.right,B);
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null) return false;
//找到相同的节点后，判断B是否是A的子结构
if(A.val == B.val && (helper(A.left,B.left) && helper(A.right,B.right))) {
return true;
}
//找到与B根节点相同的节点
return isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
public boolean helper(TreeNode root1, TreeNode root2) {
//root2为空则可确认B是A的子结构 此处的if判断顺序不能颠倒
if(root2 == null) return true;
//root1为空，说明B不是A的子结构
if(root1 == null) return false;
//如果A、B值相同，则继续判断其子节点
if(root1.val == root2.val) {
return helper(root1.left,root2.left) && helper(root1.right,root2.right);
}else {
return false;
}
}
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点。注意：两节点之间的路径长度是以它们之间边的数目表示的。
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
后序遍历二叉树，在遍历的同时记录每个节点的最大直径（左子树深度+右子树深度），求出节点最大的直径。
int maxd = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return maxd;
}
public int depth(TreeNode node) {
if(node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
maxd = Math.max(left + right,maxd); //将每个节点的最大直径（左子树深度 + 右子树深度）与当前最大值进行比较并取大者
return Math.max(left,right) + 1; //返回节点深度
}
二叉树中的最大路径和
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。给你一个二叉树的根节点root，返回其最大路径和。
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
traversal(root);
return result;
}
//后序遍历 因为要利用左右节点的返回值 完成最大路径和的选取
public int traversal(TreeNode root) {
if(root == null) return 0;
//只有左右节点的值大于0时，才会选取对应的左右子节点
int left = Math.max(traversal(root.left),0);
int right = Math.max(traversal(root.right),0);
//比较每个节点的最大路径总和
result = Math.max(left + right + root.val,result);
//返回节点的最大路径和
return Math.max(left,right) + root.val;
}
二叉树的坡度
给你一个二叉树的根节点root，计算并返回整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树的节点之和的差的绝对值。如果没有左子树的话，左子树的节点之和为0；没有右子树的话也是一样。空节点的坡度是0。整个树的坡度就是其所有节点的坡度之和。
输入：root = [4,2,9,3,5,null,7]
输出：15
解释：
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 5 的坡度：|0-0| = 0（没有子节点）
节点 7 的坡度：|0-0| = 0（没有子节点）
节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15
累计二叉树中所有节点的左子树节点之和与右子树节点之和的差的绝对值。因此，可以使用深度优先搜索，在遍历每个节点时，累加其左子树节点之和与右子树节点之和的差的绝对值，并返回以其为根节点的树的节点之和。
int result = 0;
public int findTilt(TreeNode root) {
traversal(root);
return result;
}
public int traversal(TreeNode root) {
if(root == null) return 0;
int sumLeft = traversal(root.left);
int sumRight = traversal(root.right);
result += Math.abs(sumLeft - sumRight);
return sumRight + sumLeft + root.val;
}
路径总和II
给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的(只能从父节点到子节点)。
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
定义节点的前缀和为：由根节点到当前节点的路径上所有节点的和。利用先序遍历，记录下根节点root到当前节点p的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和curr减去targetSum。
- 对于空路径也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为0。
- 假设根节点为root，当前刚好访问节点node，则此时从根节点到节点node的路径（无重复节点）刚好为root->p1->p2->...->pk->node，此时已经保存了节点p1,p2,p3,...pk的前缀和，并且计算出了节点node的前缀和。
- 假设当前从根节点root到节点node的前缀和为curr，则此时在已保存的前缀和查找是否存在前缀和刚好等于curr-targetSum。假设从根节点root到节点node的路径中存在pi到根节点root的前缀和为curr-targetSum，则节点pi+1到node的路径上所有节点的和一定为targetSum。
- 利用深度搜索遍历树，当退出当前节点时，需要及时更新已经保存的前缀和。
private int ans = 0;
public int pathSum(TreeNode root, int targetSum) {
//前缀和+哈希表：先遍历从根节点开始到叶子节点的每一条路径，求出这条路径的前缀和，前缀和保存到哈希表，在求的过程中根据哈希表统计答案。
Map<Integer,Integer> sum = new HashMap<Integer,Integer>();
sum.put(0,1); //初始化
dfs(root,0,sum,targetSum);
return ans;
}
public void dfs(TreeNode node,int pre,Map<Integer,Integer> sum,int targetSum) {
if(node == null) return;
pre += node.val; //当前前缀和
ans += sum.getOrDefault(pre - targetSum,0); //统计答案
sum.put(pre,sum.getOrDefault(pre,0) + 1); //哈希表加入当前前缀和
dfs(node.left,pre,sum,targetSum);
dfs(node.right,pre,sum,targetSum);
sum.put(pre,sum.get(pre) - 1); //哈希表删除当前前缀和(复原)
}
序列化和反序列化二叉搜索树
设计一个算法来序列化和反序列化二叉搜索树。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
输入：root = [2,1,3]
输出：[2,1,3]
输入：root = []
输出：[]
序列化时，只需要对二叉搜索树进行后序遍历，再将数组编码成字符串即可。
反序列化时，需要先将字符串解码成后序遍历的数组。再将后序遍历的数组恢复成二叉搜索树时，不需要先排序得到中序遍历的数组再根据中序和后序的数组来恢复二叉树，而可以根据有序性直接由后序遍历的数组恢复二叉搜索树。后序遍历得到的数组中，根节点的值位于数组末尾，左子树的节点均小于根节点的值，右子树的节点均大于根节点的值，可以根据这些性质设计递归函数恢复二叉搜索树。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
List<Integer> list = new ArrayList<>();
postOrder(root,list);
String str = list.toString();
return str.substring(1,str.length() - 1);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.isEmpty()) return null;
Deque<Integer> stack = new ArrayDeque<Integer>();
String[] arr = data.split(", ");
for(int i = 0; i < arr.length; i++) {
stack.push(Integer.parseInt(arr[i]));
}
return construct(Integer.MIN_VALUE,Integer.MAX_VALUE,stack);
}
private void postOrder(TreeNode root,List<Integer> list) {
if(root == null) return ;
postOrder(root.left,list);
postOrder(root.right,list);
list.add(root.val);
}
private TreeNode construct(int lower,int upper,Deque<Integer> stack) {
if(stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
return null;
}
int val = stack.pop();
TreeNode root = new TreeNode(val);
root.right = construct(val,upper,stack);
root.left = construct(lower,val,stack);
return root;
}
}
二叉树的序列化与反序列化
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
可以先序遍历这颗二叉树，遇到空子树的时候序列化成None，否则继续递归序列化。反序列化则需要根据","把原先的序列分割开来得到先序遍历的元素列表，然后从左向右遍历这个序列：
- 如果当前的元素为None，则当前为空树
- 否则先解析这棵树的左子树，再解析它的右子树
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return reserialize(root,"");
}
public String reserialize(TreeNode root, String str) {
if(root == null) {
str += "None,";
}else {
str += str.valueOf(root.val) + ",";
str = reserialize(root.left,str);
str = reserialize(root.right,str);
}
return str;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] dataArray = data.split(",");
List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
return rdeserialize(dataList);
}
public TreeNode rdeserialize(List<String> dataList) {
if(dataList.get(0).equals("None")) {
dataList.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
root.left = rdeserialize(dataList);
root.right = rdeserialize(dataList);
return root;
}
}
根据二叉树创建字符串
给你二叉树的根节点root，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。空节点使用一对空括号对"()"表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
可以使用递归的方法得到二叉树的前序遍历，并在递归时加上额外的括号。
-
如果当前节点有两个孩子，那在递归时，需要在两个孩子的结果外都加上一层括号；
-
如果当前节点没有孩子，那不需要在节点后面加任何括号。
- 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
- 如果当前节点只有右孩子，那在递归时，需要先加上一层空的括号"()"表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。
public String tree2str(TreeNode root) {
if(root == null) return "";
if(root.left == null && root.right == null) return Integer.toString(root.val);
if(root.right == null) return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
}
迭代法：
public String tree2str(TreeNode root) {
StringBuffer ans = new StringBuffer();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
stack.push(root);
Set<TreeNode> visited = new HashSet<>();
while(!stack.isEmpty()) {
TreeNode node = stack.peek();
if(!visited.add(node)) {
if(node != root) {
ans.append(")");
}
stack.pop();
} else {
if(node != root) {
ans.append("(");
}
ans.append(node.val);
if(node.left == null && node.right != null) {
ans.append("()");
}
if(node.right != null) {
stack.push(node.right);
}
if(node.left != null) {
stack.push(node.left);
}
}
}
return ans.toString();
}
二叉树中所有距离为K的节点
给定一个二叉树（具有根节点root），一个目标节点target和一个整数值k。返回到目标节点target距离为k的所有节点的值的列表。答案可以以任何顺序返回。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1
输入: root = [1], target = 1, k = 3
输出: []
若将target当作树的根节点，我们就能从target出发，使用深度优先搜索去寻找与target距离为k的所有节点，即深度为k的所有节点。
由于输入的二叉树没有记录父节点，为此，从根节点root出发，使用深度优先搜索遍历整棵树，同时用一个哈希表记录每个节点的父节点。然后从target出发，使用深度优先搜索遍历整棵树，除了搜索左右儿子外，还可以顺着父节点向上搜索。
代码实现时，由于每个节点值都是唯一的，哈希表的键可以用节点值代替。此外，为避免在深度优先搜索时重复访问节点，递归时额外传入来源节点from，在递归前比较目标节点是否与来源节点相同，不同的情况下才进行递归。
Map<Integer,TreeNode> parents = new HashMap<Integer,TreeNode>();
List<Integer> ans = new ArrayList<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
//从root出发DFS，记录每个节点的父节点
findParents(root);
//从target出发DFS，寻找所有深度为k的节点
findAns(target,null,0,k);
return ans;
}
//记录每个节点的父节点
public void findParents(TreeNode node) {
if(node.left != null) {
parents.put(node.left.val,node);
findParents(node.left);
}
if(node.right != null) {
parents.put(node.right.val,node);
findParents(node.right);
}
}
public void findAns(TreeNode node, TreeNode from,int depth,int k) {
if(node == null) return;
//记录与target距离为k的所有节点的值
if(depth == k) {
ans.add(node.val);
return;
}
//防止顺着父节点向上搜索时，重复访问节点
if(node.left != from) {
findAns(node.left,node,depth + 1,k);
}
if(node.right != from) {
findAns(node.right,node,depth + 1,k);
}
//用三分支递归实现搜索target父节点
if(parents.get(node.val) != from) {
findAns(parents.get(node.val),node,depth + 1,k);
}
}
二叉树的堂兄弟节点
在二叉树中，如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。给出了具有唯一值的二叉树的根节点root，以及树中两个不同节点的值x和y。只有与值x和y对应的节点是堂兄弟节点时，才返回true。否则返回false。
输入：root = [1,2,3,4], x = 4, y = 3
输出：false
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
可以从根节点开始，对树进行一次遍历，在遍历的过程中维护深度以及父节点这两个信息。当遍历到x或y节点时，就将信息记录下来；当这两个节点都遍历完成了以后，就可以退出遍历的过程，判断它们是否为堂兄弟节点了。
深度优先搜索：
//x的信息
int x;
TreeNode xParent;
int xDepth;
boolean xFound = false;
//y的信息
int y;
TreeNode yParent;
int yDepth;
boolean yFound = false;
public boolean isCousins(TreeNode root, int x, int y) {
this.x = x;
this.y = y;
dfs(root,0,null);
return xDepth == yDepth && xParent != yParent;
}
public void dfs(TreeNode node,int depth,TreeNode parent) {
if(node == null) return;
if(node.val == x) {
xParent = parent;
xDepth = depth;
xFound = true;
}else if(node.val == y) {
yParent = parent;
yDepth = depth;
yFound = true;
}
if(xFound && yFound) return;
dfs(node.left,depth + 1,node);
dfs(node.right,depth + 1,node);
}
从根到叶的二进制数之和
给出一棵二叉树，其上每个节点的值都是0或1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
- 例如，如果路径为
0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数01101，也就是13。
对树上的每一片叶子，我们都要找出从根到叶子的路径所表示的数字。返回这些数字之和。
输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
深度优先搜索：
public int sumRootToLeaf(TreeNode root) {
return traversal(root,0);
}
public int traversal(TreeNode root,int count) {
if(root == null) return 0;
count = 2 * count + root.val;
if(root.left == null && root.right == null) {
return count;
}
return traversal(root.left,count) + traversal(root.right,count);
}
二叉树的垂序遍历
给你二叉树的根节点root，请你设计算法计算二叉树的垂序遍历序列。对位于(row,col)的每个节点而言，其左右子节点分别位于(row + 1,col - 1)和(row + 1，col + 1)。树的根节点位于(0,0)。二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有节点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个节点，则按节点的值从小到大进行排序。返回二叉树的垂序遍历序列。
输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。
根据题意，我们需要按照优先级（列号从小到大，对于同列节点，行号从小到大，对于同列同行元素，节点值从小到大）进行答案构造。因此可以对树进行遍历，遍历过程中记下这些信息(col,row,val)，然后根据规则进行排序，并构造答案。可以先使用哈希表进行存储，最后再进行一次性的排序。
Map<TreeNode,int[]> map = new HashMap<>(); //col,row,val
public List<List<Integer>> verticalTraversal(TreeNode root) {
map.put(root,new int[]{0,0,root.val});
dfs(root);
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>> result = new ArrayList<>();
for(int i = 0; i < list.size();) {
int j = i;
List<Integer> temp = new ArrayList<>();
while(j < list.size() && list.get(j)[0] == list.get(i)[0]) temp.add(list.get(j++)[2]);
result.add(temp);
i = j;
}
return result;
}
public void dfs(TreeNode root) {
if(root == null) return ;
int[] info = map.get(root);
int col = info[0], row = info[1], val = info[2];
if(root.left != null) {
map.put(root.left,new int[]{col - 1,row + 1, root.left.val});
dfs(root.left);
}
if(root.right != null) {
map.put(root.right,new int[]{col + 1,row + 1,root.right.val});
dfs(root.right);
}
}
投递清华大学等公司8个岗位
滴滴公司福利 1042人发布
百度一面666人在聊