二叉树¶
1. 二叉树介绍¶
1.1 二叉树分类¶
满二叉树： 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
度的概念：
在树结构中，度 是指一个节点拥有的子节点数量。对于二叉树来说，每个节点最多有两个子节点，因此其度数最大为2。 - 如果一个节点没有子节点，那么它的度数为0，称为叶子节点或者叶子。 - 如果一个节点有一个子节点，那么它的度数为1。 - 如果一个节点有两个子节点，那么它的度数为2。
这棵二叉树为满二叉树，也可以说深度为\(k\)，有 \(2^k-1\) 个节点的二叉树。
深度的定义:
- 树的深度是指从根节点到最深层节点的路径长度，也可以理解为树中最长路径的长度。
- 换句话说，树的深度是根节点到最深叶子节点的距离。在某些情况下，也可以将树的深度称为高度。
完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1 ~ \(2^{(h-1)}\) 个节点。
二叉搜索树： 二叉搜索树是一个有序树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树： 又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
1.2 二叉树的存储方式¶
链式存储： 链式存储方式使用指针，通过指针把分布在各个地址上的节点串联起来
链式存储如图：
顺序存储: 顺序存储使用数组，顺序存储的元素在内存是连续分布的
顺序存储如图：
如何遍历用数组存储的二叉树：
如果父节点的数组下标是 i，那么它的左孩子就是 \(i * 2 + 1\)，右孩子就是 \(i * 2 + 2\)。
1.3 二叉树的遍历¶
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
深度优先遍历： - 前序遍历（递归法，迭代法） - 中序遍历（递归法，迭代法） - 后序遍历（递归法，迭代法）
广度优先遍历： - 层次遍历（迭代法）
深度优先遍历中：有三个顺序，前中后序遍历，这里前中后，其实指的就是中间节点的遍历顺序。
前中后序遍历的逻辑都是可以借助栈使用递归的方式来实现。
广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
1.4 二叉树的定义¶
链式存储的二叉树节点的定义方式：
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode();
TreeNode(int val) { this.val = val};
TreeNode(int val, TreeNode left, TreeNode right){
this.val = val;
this.left = left;
this.right = right;
}
}
1.5 二叉树的高度和深度¶
深度和高度：
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
leetcode中强调的深度和高度很明显是按照节点来计算的
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
2. 二叉树的递归遍历¶
递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证写出正确的递归算法！
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
二叉树的前序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
preorder(root, resList);
return resList;
}
// 前序遍历
public void preorder(TreeNode node, List resList){
if (node == null) return;
resList.add(node.val);
preorder(node.left, resList);
preorder(node.right, resList);
}
}
二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
inorder(root, resList);
return resList;
}
public void inorder(TreeNode node, List resList){
if (node == null) return;
inorder(node.left, resList);
resList.add(node.val);
inorder(node.right, resList);
}
}
二叉树的后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
postorder(root, resList);
return resList;
}
// 后序遍历
public void postorder(TreeNode node, List resList){
if (node == null) return;
postorder(node.left, resList);
postorder(node.right, resList);
resList.add(node.val);
}
}
3. 二叉树的迭代遍历¶
用栈实现二叉树的前中后序遍历
前序遍历
前序遍历的顺序是 中左右，而栈是后进先出
因此按照 根节点 右孩子 左孩子 的顺序入栈
每一次根节点入栈，然后判断是否为空，不为空则弹出
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
// 使用栈实现前序遍历
Stack<TreeNode> stack = new Stack<>();
if (root == null) return resList;
// root 入栈
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
resList.add(node.val);
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
}
return resList;
}
}
中序遍历
中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中）（即最后访问的最先处理，而且放入到栈中的都是左节点）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 使用栈实现中序遍历
List<Integer> resList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
// 遍历树, 找到左节点
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
// 已经找到最左边的节点, 栈顶即为最左边的节点
TreeNode node = stack.pop();
resList.add(node.val);
// 现在栈顶为中间节点
cur = node.right;
}
}
return resList;
}
}
后序遍历
后序遍历为 左右中，修改前序遍历为 中右左，然后反转结果变为 左右中
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return resList;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
resList.add(node.val);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
Collections.reverse(resList);
return resList;
}
}
4. 二叉树的统一迭代法¶
将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记
标记法：要处理的节点放入栈之后，紧接着放入一个空指针作为标记
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return resList;
stack.push(root);
while(!stack.isEmpty()){
// 因为使用空节点进行标记, 因此需要判断是否为空
TreeNode node = stack.peek();
// 如果为空, 则需要将下一个节点加入结果集中
if (node == null){
stack.pop();
TreeNode theNode = stack.pop();
resList.add(theNode.val);
}
// 继续向下遍历, 直到找到最左边的节点
else{
// 先弹出, 避免重复
stack.pop();
// 按照 右 中 左的顺序入栈
if (node.right != null) stack.push(node.right);
stack.push(node);
stack.push(null); // 空节点作为标记
if (node.left != null) stack.push(node.left);
}
}
return resList;
}
}
前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return resList;
stack.push(root);
while(!stack.isEmpty()){
// 因为使用空节点进行标记, 因此需要判断是否为空
TreeNode node = stack.peek();
// 如果为空, 则需要将下一个节点加入结果集中
if (node == null){
stack.pop();
TreeNode theNode = stack.pop();
resList.add(theNode.val);
}
// 继续向下遍历, 直到找到最左边的节点
else{
// 先弹出, 避免重复
stack.pop();
// 按照 右 左 中的顺序入栈
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
stack.push(node);
stack.push(null); // 空节点作为标记
}
}
return resList;
}
}
后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> resList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return resList;
stack.push(root);
while(!stack.isEmpty()){
// 因为使用空节点进行标记, 因此需要判断是否为空
TreeNode node = stack.peek();
// 如果为空, 则需要将下一个节点加入结果集中
if (node == null){
stack.pop();
TreeNode theNode = stack.pop();
resList.add(theNode.val);
}
// 继续向下遍历, 直到找到最左边的节点
else{
// 先弹出, 避免重复
stack.pop();
// 按照 右 左 中的顺序入栈
stack.push(node);
stack.push(null); // 空节点作为标记
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
return resList;
}
}
5. 二叉树的层序遍历¶
使用队列实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resList = new ArrayList<>();
// 使用队列实现 先进先出
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int len = queue.size();
for (int i=0; i<len; i++){
TreeNode node = queue.poll();
list.add(node.val);
// 从左向右 先进先出
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
resList.add(list);
}
return resList;
}
}
5.1 二叉树的层序遍历Ⅱ¶
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> resList = new ArrayList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
List<Integer> list = new ArrayList<>();
while(len-- > 0){
TreeNode node = queue.poll();
list.add(node.val);
// 当前节点的左右子树添加到队列中
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
resList.add(list);
}
List<List<Integer>> resList2 = new ArrayList<>();
for (int i=resList.size()-1; i>=0; i--){
resList2.add(resList.get(i));
}
return resList2;
}
}
5.2 二叉树的右视图¶
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> resList = new ArrayList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
while(len-- > 0){
TreeNode node = queue.poll();
// 只有当队列中只剩下一个元素的时候, 由于队列先进先出的性质, 剩下的一个元素一定是最靠右的
if (len == 0) resList.add(node.val);
// 当前节点的左右子树添加到队列中
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return resList;
}
}
5.3 二叉树的层平均值¶
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
List<Double> resList = new ArrayList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
// 记录节点的值的和
// 最好定义Double, 不然 最后乘1.0会出现问题
Double sum = 0.0;
for (int i=0; i<len; i++){
TreeNode node = queue.poll();
sum += node.val;
// 当前节点的左右子树添加到队列中
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
resList.add(sum / len);
}
return resList;
}
}
5.3 N叉树的层序遍历¶
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
// 使用队列实现
Queue<Node> queue = new LinkedList<>();
List<List<Integer>> resList = new ArrayList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
List<Integer> list = new ArrayList<>();
while(len-- > 0){
Node node = queue.poll();
list.add(node.val);
List<Node> childrenNodes = node.children;
for (int i=0; i<childrenNodes.size(); i++){
queue.offer(childrenNodes.get(i));
}
}
resList.add(list);
}
return resList;
}
}
5.4 在每个树行中找最大值¶
class Solution {
public List<Integer> largestValues(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> resList = new ArrayList<>();
if (root == null) return resList;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
int max = Integer.MIN_VALUE;
while(len-- > 0){
TreeNode node = queue.poll();
int temp = node.val;
max = max > temp?max:temp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
resList.add(max);
}
return resList;
}
}
5.5 填充每个节点的下一个右侧节点指针¶
class Solution {
public Node connect(Node root) {
// 使用队列实现
Queue<Node> queue = new LinkedList<>();
List<Integer> resList = new ArrayList<>();
if (root == null) return root;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
for (int i=0; i<len; i++)
{
Node node = queue.poll();
// 当为该层的最右边的节点时, next指向空
if(i == len-1) node.next = null;
// 否则指向右边的节点
else{
node.next = queue.peek();
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return root;
}
}
5.6 二叉树的最大深度¶
class Solution {
public int maxDepth(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
int maxDepth = 0;
if (root == null) return maxDepth;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
maxDepth++;
while(len-- > 0){
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return maxDepth;
}
}
5.7 二叉树的最小深度¶
class Solution {
public int minDepth(TreeNode root) {
// 使用队列实现
Queue<TreeNode> queue = new LinkedList<>();
int minValue = 0;
if (root == null) return minValue;
queue.offer(root);
while(!queue.isEmpty()){
// 保存当前层的节点个数
int len = queue.size();
while(len-- > 0){
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
minValue++;
return minValue;
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
minValue++;
}
return minValue;
}
}
6. 反转二叉树¶
思路： 反转每一个节点的左右孩子
递归法
class Solution {
public TreeNode invertTree(TreeNode root) {
reverse(root);
return root;
}
public void reverse(TreeNode node){
if (node == null) return;
TreeNode temp = node.left;
node.left=node.right;
node.right=temp;
reverse(node.left);
reverse(node.right);
}
}
迭代法
class Solution {
public TreeNode invertTree(TreeNode root) {
// 使用迭代法
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
if (root == null) return root;
while(!stack.isEmpty()){
// 获得 根节点
TreeNode node = stack.pop();
TreeNode temoNode = node.left;
node.left = node.right;
node.right = temoNode;
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return root;
}
}
层序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
// 层序遍历
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) return root;
queue.offer(root);
while(!queue.isEmpty()){
int len = queue.size();
for (int i=0; i<len; i++){
TreeNode node = queue.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return root;
}
}
7. 对称二叉树¶
方法一：迭代法
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) return true;
// 使用队列存储 左右节点
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
int len = queue.size();
for (int i=0; i< len; i+=2){
// 左节点和右节点比较
TreeNode leftNode = queue.poll();
TreeNode rightNode = queue.poll();
// 都是空的, 则继续
if (leftNode == null && rightNode == null) continue;
// 一个是空的, 一个不为空, 则必定不是对称的
else if (leftNode == null && rightNode != null) return false;
else if (leftNode != null && rightNode == null) return false;
// 都不为空
else if (leftNode.val != rightNode.val) return false;
else if (leftNode.val == rightNode.val){
// 将左节点的左孩子和右节点的右孩子添加到队列中
queue.offer(leftNode.left);
queue.offer(rightNode.right);
queue.offer(leftNode.right);
queue.offer(rightNode.left);
}
}
}
return true;
}
}
注意：该方法是用队列来存储需要比较的元素, 而不是层次遍历
方法二：递归法
只能使用后序遍历
思考：对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，其实要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中
递归三部曲：
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
- 确定终止条件
节点为空的情况：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
- 左节点为空，右节点不为空，不对称，return false
- 左不为空，右为空，不对称 return false
- 左右都为空，对称，返回true
左右节点不为空：
-
左右都不为空，比较节点数值，不相同就return false
-
确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
- 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
class Solution {
public boolean isSymmetric(TreeNode root) {
// 使用递归实现
if (root == null) return true;
return compare(root.left, root.right);
}
public boolean compare(TreeNode leftNode, TreeNode rightNode){
// 如果都是空, 则为终止条件, 不再处理, 直接返回false
if (leftNode == null && rightNode == null) return true;
else if (leftNode != null && rightNode == null) return false;
else if (leftNode == null && rightNode != null) return false;
else if (leftNode.val != rightNode.val) return false;
// 都不为空, 且数值相等, 说明需要进入下一层, 进入下一层递归
else if (leftNode.val == rightNode.val){
// 左节点左孩子 和 右节点右孩子
boolean cc = compare(leftNode.left, rightNode.right);
// 左节点右孩子 和 右节点左孩子
boolean cc2 = compare(leftNode.right, rightNode.left);
return cc && cc2;
}
return true;
}
}
8. 完全二叉树的节点数¶
方法一：递归
使用后序遍历
-
确定递归函数的参数和返回值：参数就是传入树的根节点，返返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
-
确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
-
- 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
class Solution {
// 使用递归
public int countNodes(TreeNode root) {
return postCount(root);
}
public int postCount(TreeNode node){
if (node == null) return 0;
// 后序遍历
// 左子树的节点数
int l = postCount(node.left);
// 右子树的节点数
int r = postCount(node.right);
// 需要加上根节点
return l+r+1;
}
}
方法二：迭代法：
使用层次遍历
class Solution {
// 使用递归
// 后序遍历
public int countNodes(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int resNum = 0;
if (root == null) return resNum;
queue.offer(root);
while (!queue.isEmpty()) {
int len = queue.size();
for (int i = 0; i < len; i++) {
TreeNode node = queue.poll();
resNum++;
// 从左向右 先进先出
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return resNum;
}
}
方法三：使用性质
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
若最底层为第 h 层，则该层包含 \(1 - 2^{(h-1)}\) 个节点。
即 全二叉树只有两种情况， - 情况一：就是满二叉树 - 情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 \(2^{(树深度 - 1)}\) 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
如图所示：
如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
判断方法：在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树
在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树
代码：
9. 平衡二叉树¶
题目重点：
一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
深度和高度：
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
leetcode中强调的深度和高度很明显是按照节点来计算的
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
本题思路：
要求比较高度，必然是要后序遍历。
递归三部曲：
- 参数和返回值 参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度。 如何标记左右子树是否差值大于1？ 如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
-
明确终止条件 遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
-
单层递归的逻辑 分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
代码：
class Solution {
public boolean isBalanced(TreeNode root) {
// 平衡二叉树: 左右两子树的高度差不能大于一
// 高度：当前节点到叶节点经过的节点数目
// 只能使用后序遍历
int res = getDepth(root);
if (res == -1) return false;
else return true;
}
// 获得根节点所在的高度
public int getDepth(TreeNode root){
// 终止条件, root=null 空节点的高度为0
if (root == null) return 0;
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
// 得到左子树的高度
int leftDepth = getDepth(leftNode);
// 如果是-1, 表示左子树不是平衡二叉树, 直接返回-1
if (leftDepth == -1) return -1;
// 得到右子树的高度
int rightDepth = getDepth(rightNode);
if (rightDepth == -1) return -1;
// 判断两者的差值
// 如果大于1, 直接返回-1, 表示该二叉树不是平衡二叉树
if (Math.abs(leftDepth - rightDepth) > 1) return -1;
// 如果不大于1, 返回以root为根节点的树的高度
return 1 + Math.max(leftDepth, rightDepth);
}
}
10. 二叉树的所有路径¶
本题思路：
要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
显然，要寻找所有的路径，需要我们中前序遍历的时候把路径都记录下来。并且需要回溯来回退一个路径再进入另一个路径。
前序遍历以及回溯的过程如图：
首先使用递归实现前序遍历
-
参数和返回值 传入根节点，记录每一条路径的path；存放结果集的result
-
终止条件 空节点，但是其实找到叶子节点就可以结束处理逻辑了，即当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。
找到叶子节点后，此时path中存储的是路径中的节点，只需要将path中存储的节点转换为string，即可得到从根节点到当前叶子节点的路径
-
单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中
然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。所以递归前要加上判断语句。
递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。 回溯和递归是一一对应的，有一个递归，就要有一个回溯
if (cur->left) {
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) {
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
// 使用pathList记录访问的路径
List<Integer> pathList = new ArrayList<Integer>();
List<String> resList = new ArrayList<>();
// 如果根节点为空, 则直接返回空集
if (root == null) return resList;
// 进行递归
traversal(root, pathList, resList);
return resList;
}
public void traversal(TreeNode root, List pathList, List resList){
// 前序遍历, 先添加中间节点
pathList.add(root.val);
// 确定终止条件
if (root.left==null && root.right==null){
// 此时访问到了叶子节点, 而pathList存储的是路径上的节点
// 需要将pathList转换为String, 即可得到从根节点到当前节点的路径
StringBuilder sb = new StringBuilder();
for (int i=0; i<pathList.size()-1;i++){
// 因为叶子节点的后面没有箭头, 所以是遍历到倒数第二个值
sb.append(pathList.get(i)).append("->");
}
sb.append(pathList.get(pathList.size()-1));
resList.add(sb.toString());
return;
}
// 单层循环的逻辑
if (root.left != null){
traversal(root.left, pathList, resList);
// 回溯
pathList.remove(pathList.size()-1);
}
if (root.right != null){
traversal(root.right, pathList, resList);
// 回溯
pathList.remove(pathList.size()-1);
}
}
}
11. 左叶子之和¶
思路
首先注意，是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。
左叶子的定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点 即判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
判断代码如下：
if (curNode.left != null && curNode.left.left == null && curNode.left.right == null){
// curNode.left 是左叶子
// 进行处理
}
使用递归
-
确定参数和返回值 传入当前节点，返回值为数值之和（所有左叶子的和）
-
确定终止条件 当前节点为空 但是需要质疑，无法判断当前节点是不是左叶子，只有通过当前节点的父节点才能进行判断
if (curNode == null) return 0; if (curNode.left == null && curNode.right == null) return 0; -
确定单层处理逻辑 遇到左叶子，记录数值。 通过递归求左子树左叶子的和 通过递归求右子树左叶子的和 将两者相加
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
// 当前节点为叶子节点
if (root.left == null && root.right == null) return 0;
// 单层递归逻辑
// 获取左子树的左叶子数值和
int leftValue = sumOfLeftLeaves(root.left);
// 如果当前节点的左孩子节点就是叶子节点
if (root.left != null && root.left.left == null && root.left.right == null) leftValue = root.left.val;
// 获取右子树的左叶子数值和
int rightValue = sumOfLeftLeaves(root.right);
return leftValue+rightValue;
}
}
使用迭代法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
// 使用迭代法实现
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) return 0;
stack.push(root);
int res = 0;
while(!stack.isEmpty()){
TreeNode curNode = stack.pop();
// 判断当前节点的左孩子是否是左叶子
if (curNode.left != null && curNode.left.left == null && curNode.left.right == null)
res += curNode.left.val;
// 前序遍历, 入栈顺序 中右左
if (curNode.right != null) stack.push(curNode.right);
if (curNode.left != null) stack.push(curNode.left);
}
return res;
}
}
12. 找树左下角的值¶
思路
直接使用层序遍历比较简单
使用递归
需要注意：一直向左边遍历到最后一个，并不一定是在最后一行
题目要求：在树的最后一行找到最左边的值。（首先要是最后一行，然后是最左边的值）
使用递归法，如何判断是最后一行？，其实就是深度最大的叶子节点一定是最后一行；然后使用前序遍历找到最左边
递归三部曲： 1. 确定参数和返回值 参数：根节点，int 记录最大深度 返回值：不需要返回值
-
确定终止条件 遇到叶子节点，统计当前叶子节点的深度， 并更新最大深度
-
确定单层递归的逻辑 找到一个叶子节点后，需要回溯，因为当前叶子节点不一定在最后一行
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int maxDepth = -1;
int res = 0;
public int findBottomLeftValue(TreeNode root) {
// 使用递归实现
if (root == null) return res;
int depth = 1;
traversal(root, depth);
return res;
}
public void traversal(TreeNode curNode, int depth){
if (curNode == null) return;
// 如果当前节点是叶子节点
if (curNode.left == null && curNode.right == null){
if (depth > maxDepth){
maxDepth = depth;
res = curNode.val;
}
return;
}
// 如果当前节点不为null并且不是叶子节点, 则继续递归
if (curNode.left != null){
// 提前进行加1
depth++;
traversal(curNode.left, depth);
// 进行回溯
depth--;
}
if (curNode.right != null){
depth++;
traversal(curNode.right, depth);
// 进行回溯
depth--;
}
return;
}
}
使用层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 使用层序遍历
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 0;
while(!queue.isEmpty()){
int size = queue.size();
for (int i=0; i<size; i++){
TreeNode curNode = queue.poll();
if (i == 0) res = curNode.val;
if (curNode.left != null) queue.offer(curNode.left);
if (curNode.right != null) queue.offer(curNode.right);
}
}
return res;
}
}
13. 路径总和¶
自己的思路
递归实现：
-
确定参数和返回值 参数：根节点和目标值（需要判断是否和目标值相等） 返回值：返回 boolean，从而判断是否有路径和和目标值相等
-
确定终止条件 遇到叶子节点就中止
-
单层循环逻辑
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int cnt = 0;
public boolean hasPathSum(TreeNode root, int targetSum) {
// 使用递归实现
if (root == null) return false;
// 确认参数和返回值
cnt += root.val;
return cntPath(root, targetSum);
}
public boolean cntPath(TreeNode root, int targetSum){
// 终止条件 到叶子节点
if (root.left == null && root.right == null){
if (cnt == targetSum)
return true;
else
return false;
}
boolean leftTree = false;
boolean rightTree = false;
// 单层循环的逻辑
if (root.left != null){
cnt += root.left.val;
leftTree = cntPath(root.left, targetSum);
cnt -= root.left.val; // 进行回溯
}
if (root.right != null){
cnt += root.right.val;
rightTree = cntPath(root.right, targetSum);
cnt -= root.right.val;
}
return leftTree || rightTree;
}
}
补充：关于返回值
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点： - 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii） - 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍） - 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
14. 根据中序和后序遍历重构二叉树¶
题目链接：LeetCode106
思路：
中序遍历：左中右 后序遍历：左右中
理论上来讲：以后序数组的最后一个元素为切割点，先切中序数组，得到左子树（左中序）和右子树（右中序）；根据中序数组得到的左中序的长度，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。如图所示：
具体步骤如下：
- 后序数组大小为0，说明根节点就是空节点，直接返回
- 如果后序数组不为空，那么取后序数组的最后一个元素作为节点元素
- 找到后序数组最后一个元素在中序数组的位置，作为切割点
- 切割中序数组，切成 中序左数组（左子树） 和 中序右数组（右子树）
- 根据上一步得到的中序左数组的长度，切割后序数组，切成后序左数组（左子树）和后序有数组（右子树）
- 递归处理左区间和右区间
伪代码如下：
TreeNode traversal(List inorder, List postorder){
// 1.后序数组大小为0，说明根节点就是空节点，直接返回
if (postorder.size() == 0) return null;
// 2.如果后序数组不为空，那么取后序数组的最后一个元素作为节点元素
int rootValue = postorder[postorder.size()-1];
TreeNode root = new TreeNode(rootValue);
// 如果后序数组只有一个元素，则该元素就是叶子节点
if (postorder.size() == 1) return root;
// 3.在中序数组中找切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
if (inorder[delimiterIndex] == rootValue) break;
}
// 4. 切割中序数组，得到 中序左数组（左子树） 和 中序右数组
// 5. 根据上一步得到的中序左数组的长度，切割后序数组，得到后序左数组（左子树）和后序有数组（右子树）
// 6. 递归处理左区间和右区间
root.left = traversal(中序左数组, 后序左数组)
root.right = traversal(中序右数组, 后序有数组)
return root
}
难点：如何切割数组？ 始终遵循一个原则，要么左闭右开，要么左闭右闭 下面遵循 左闭右开的原则
首先进行中序数组的切割： 找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，
// 找到中序数组中的切割点
int delimiterIndex;
for (delimiterInedx = 0; delimiterInedx < inorder.size(); delimiterInedx++){
if (inorder[delimiterInedx] == rootValue) break;
}
// 遵循左闭右开 [0, delimiterIndex)
// [inorderStart, delimiterIndex)
List leftInorder;
// [delimiterIndex+1, inorderEnd)
// [delimiterIndex+1, inorder.size())
List rightInorder;
然后切割后序数组：
根据上一步得到的左中序数组的长度
// 左闭右开 [0,leftInorder.size())
// [postorderStart, postorderStart+leftInorder.size())
List leftPostorder;
// [leftInorder.size(), postorderEnd]
// [postorderStart+leftInorder.size(), postorderEnd)
List rightPostorder;
完整代码实现： ·
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 1. 如果后序数组为空，直接返回null
if (postorder.length == 0) return null;
// 采用左闭右开的方法
int inorderStart = 0;
int inorderEnd = inorder.length;
int postorderStart = 0;
int postorderEnd = postorder.length;
// 通过索引来分割数组
return transveral(inorder, inorderStart, inorderEnd, postorder, postorderStart, postorderEnd);
}
public TreeNode transveral(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
// 1. 如果后序数组的开始索引和结束索引相同，则都取不到，返回null
if (postorderEnd == postorderStart) return null;
// 2.取后序数组的最后一个元素，即为节点元素
int rootValue = postorder[postorderEnd-1];
TreeNode rootNode = new TreeNode(rootValue);
// 如果后序数组只有一个元素, 则为叶子节点
if (postorderEnd - postorderStart == 1) return rootNode;
// 3.找到节点在中序数组中的位置，作为切割点
int delimiterIndex;
for (delimiterIndex = inorderStart; delimiterIndex < inorderEnd; delimiterIndex++){
if (inorder[delimiterIndex] == rootValue) break;
}
// 4.切割中序数组
// 中序左数组 [inorderStart, delimiterIndex]
int leftInorderStart = inorderStart;
int leftInorderEnd = delimiterIndex;
// 中序右数组 [delimiterIndex+1, inorderEnd]
int rightInorderStart = delimiterIndex+1;
int rightInorderEnd = inorderEnd;
// 5.切割后序数组
// 后序左数组 [postorderStart, postorderStart + (delimiterIndex-inorderStart)]
int leftPostorderStart = postorderStart;
int leftPostorderEnd = postorderStart + (delimiterIndex-inorderStart);
// 后序右数组 [postorderStart + (delimiterIndex-inorderStart), postorderEnd-1]
int rightPostorderStart = postorderStart + (delimiterIndex-inorderStart);
int rightPostorderEnd = postorderEnd - 1;
// 6. 进行递归
rootNode.left = transveral(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);
rootNode.right = transveral(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
return rootNode;
}
}
15. 根据前序和中序遍历重构二叉树¶
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 1. 如果前序数组为空，直接返回null
if (preorder.length == 0) return null;
// 采用左闭右开的方法
int inorderStart = 0;
int inorderEnd = inorder.length;
int preorderStart = 0;
int preorderEnd = preorder.length;
// 通过索引来分割数组
return transveral(inorder, inorderStart, inorderEnd, preorder, preorderStart, preorderEnd);
}
public TreeNode transveral(int[] inorder, int inorderStart, int inorderEnd, int[] preorder, int preorderStart, int preorderEnd){
// 1. 如果前序数组的开始索引和结束索引相同，则都取不到，返回null
if (preorderEnd == preorderStart) return null;
// 2.取前序数组的最后一个元素，即为节点元素
int rootValue = preorder[preorderStart];
TreeNode rootNode = new TreeNode(rootValue);
// 如果前序数组只有一个元素, 则为叶子节点
if (preorderEnd - preorderStart == 1) return rootNode;
// 3.找到节点在中序数组中的位置，作为切割点
int delimiterIndex;
for (delimiterIndex = inorderStart; delimiterIndex < inorderEnd; delimiterIndex++){
if (inorder[delimiterIndex] == rootValue) break;
}
// 4.切割中序数组
// 中序左数组 [inorderStart, delimiterIndex]
int leftInorderStart = inorderStart;
int leftInorderEnd = delimiterIndex;
// 中序右数组 [delimiterIndex+1, inorderEnd]
int rightInorderStart = delimiterIndex+1;
int rightInorderEnd = inorderEnd;
// 5.切割前序数组
// 前序左数组
int leftpreorderStart = preorderStart+1;
int leftpreorderEnd = preorderStart + 1 + (delimiterIndex-inorderStart);
// 前序右数组
int rightpreorderStart = preorderStart + 1 + (delimiterIndex-inorderStart);
int rightpreorderEnd = preorderEnd;
// 6. 进行递归
rootNode.left = transveral(inorder, leftInorderStart, leftInorderEnd, preorder, leftpreorderStart, leftpreorderEnd);
rootNode.right = transveral(inorder, rightInorderStart, rightInorderEnd, preorder, rightpreorderStart, rightpreorderEnd);
return rootNode;
}
}
16. 最大二叉树¶
来源：LeetCode 654
思路：
构造二叉树一般采用前序遍历，先构造中间节点，再构造左子树，然后构造右子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
// 采用左闭右开
// 1.确定参数和返回值：参数为需要遍历的数组, 数组的起始索引, 数组的终止索引（取不到）
return traversal(nums, 0, nums.length);
}
public TreeNode traversal(int[] nums, int start, int end){
// 2.确定终止条件
// 因为是左闭右开, 因此当开始索引大于等于终止索引, 说明是空的数组, 则直接返回
if (start >= end) return null;
// 3.确定单层递归的逻辑
// 3.1 找到最大值的索引
int maxIndex = start;
for (int i=start; i<end; i++){
if (nums[i] > nums[maxIndex])
maxIndex = i;
}
TreeNode root = new TreeNode(nums[maxIndex]);
// 3.2 确定最大值左边数组的开始和终止索引
int leftStart = start;
int leftEnd = maxIndex;
// 确定最大值右边数组的开始和终止索引
int rightStart = maxIndex+1;
int rightEnd = end;
root.left = traversal(nums, leftStart, leftEnd);
root.right = traversal(nums, rightStart, rightEnd);
return root;
}
}
17.合并二叉树¶
来源：Leetcode 617
前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 方法1: 使用递归
// 1.确认参数和返回值
// 传入的两个参数即为两个节点, 返回值为计算后的节点
// 2.确定终止条件
if (root1 == null) return root2;
if (root2 == null) return root1;
// 3.确定单层循环的逻辑
TreeNode newRoot = new TreeNode(root1.val + root2.val);
newRoot.left = mergeTrees(root1.left, root2.left);
newRoot.right = mergeTrees(root1.right, root2.right);
return newRoot;
}
}
层次遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 方法2：使用层次遍历
if (root1 == null) return root2;
if (root2 == null) return root1;
// 接下来以root1为基准, 所有更改都在root1上进行, 最终也返回root1
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root1);
queue.offer(root2);
while(!queue.isEmpty()){
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
node1.val = node1.val + node2.val;
if (node1.left != null && node2.left != null){
queue.offer(node1.left);
queue.offer(node2.left);
}
if (node1.right != null && node2.right != null){
queue.offer(node1.right);
queue.offer(node2.right);
}
if (node1.left == null && node2.left != null)
node1.left = node2.left;
if (node1.right == null && node2.right != null)
node1.right = node2.right;
}
return root1;
}
}
18.二叉搜索树中的搜索¶
来源：Leetcode 700
二叉搜索树的定义：
二叉搜索树是一个有序树： - 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； - 它的左、右子树也分别为二叉搜索树
思路：
使用递归实现
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
// 方法1：使用递归
// 1.确定参数和返回值
// 参数为入口节点和要查找的整数值, 返回值为寻找到的整数值所在的节点
// 2.确定终止条件
if (root == null || root.val==val) return root;
// 3,确定单层递归的条件
TreeNode resNode = null;
if (val < root.val) resNode = searchBST(root.left, val);
else if (val > root.val) resNode = searchBST(root.right, val);
return resNode;
}
}
使用迭代实现
对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，再走右分支。
而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
// 方法2: 迭代法
while(root != null){
if (root.val == val) return root;
else if (val < root.val) root = root.left;
else if (val > root.val) root = root.right;
}
return root;
}
}
19.验证二叉搜索树¶
来源：LeetCode 98
背景：二叉搜索树的概念
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
方法一：直接判断
中序遍历下，输出的二叉搜索树节点的数值是有序序列。
因为原题目 验证二叉搜索树 转变为 判断中序遍历序列是不是递增的
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
// 1. 直接判断数组是否递增
// 首先使用中序遍历将二叉树转变为数组
// 然后遍历数组确定数组是否递增
if (root == null) return true;
traversal(root);
if (list.size() <= 1) return true;
for (int i=1; i<list.size(); i++){
if (list.get(i) <= list.get(i-1)){
return false;
}
}
return true;
}
// 中序遍历
public void traversal(TreeNode root){
if (root == null) return;
traversal(root.left);
list.add(root.val);
traversal(root.right);
}
}
方法二：使用递归
- 首先确认递归函数、返回值和参数
因为需要判断是否在 中序遍历中 前一个节点的值 要小于后一个节点的值, 因此需要存储前一个节点
同时 需要 寻找是否存在 不满足条件的, 因此需要返回值 boolean
TreeNode pre = null;
boolean isValidBST(TreeNode root)'
- 确定终止条件
当 根节点为空的时候 终止
if (root == null) return;
- 确定单层循环的逻辑
一方面进行条件判读，一方面进行 pre 更新
boolean left = isValidBST(root.left);
if (pre != null && pre.val >= root.val) return false;
pre = root;
boolean right = isValidBST(root.right);
return left && right;
完整代码：
class Solution {
// 记录前一个节点, 因为在中序遍历中要求前一个节点的值要小于后一个节点的值
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
// 方法2：使用递归，直接在递归的过程中判断是否有序
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;
}
}
20.二叉搜索树的最小绝对差¶
来源：LeetCode 530
首先需要知道二叉树的特性：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
因此二叉树是有序的，因此在二叉树上求最值、差值，可以相当于在一个有序数组上求最值、差值。
方法一：将二叉搜索树转换为有序数组¶
class Solution {
int result = 100000;
List<Integer> nums = new ArrayList<>();
// 使用中序遍历遍历二叉树
public void traversal(TreeNode root){
if (root == null) return;
traversal(root.left);
nums.add(root.val);
traversal(root.right);
}
public int getMinimumDifference(TreeNode root) {
traversal(root);
for (int i=1; i<nums.size(); i++){
int temp = nums.get(i) - nums.get(i-1);
if (result > temp) result = temp;
}
return result;
}
}
方法二：在递归的过程直接计算¶
需要记录递归过程中遍历的 前一个节点，将当前节点与前一个节点做差值
class Solution {
// 直接使用递归
// 记录遍历的节点（相对于当前节点的前一个节点）
TreeNode pre = null;
int result = 100000;
// 使用中序遍历
public void traversal(TreeNode root){
if (root == null) return;
traversal(root.left);
// 得到当前节点
if (pre != null){
int temp = root.val - pre.val;
if (result > temp) result = temp;
}
pre = root;
traversal(root.right);
}
public int getMinimumDifference(TreeNode root) {
traversal(root);
return result;
}
}
21.二叉搜索树中的众数¶
来源：LeetCode 501
方法一：如果不是二叉搜索树¶
直接将树进行遍历，使用map统计每一个数字出现的频率，然后按照频率进行排序，最后取前面最高频的元素的集合
class Solution {
// map: 进行频率统计
Map<Integer, Integer> map = new HashMap<>();
// 1. 首先遍历树, 使用map统计每一个数字出现的次数
public void traversal(TreeNode root){
if (root == null) return;
// 使用前序遍历
map.put(root.val, map.getOrDefault(root.val,0) + 1);
traversal(root.left);
traversal(root.right);
}
public int[] findMode(TreeNode root) {
traversal(root);
// 2. 将map转换为 列表 进行按照频率排序（map不能直接排序）
List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(map.entrySet());
// 按照频率大小（val） 从大到小排序
entryList.sort((e1,e2)->e2.getValue().compareTo(e1.getValue()));
// 3. 取前面最高频的元素
List<Integer> results = new ArrayList<>();
int maxFrequence = entryList.get(0).getValue();
for (Map.Entry<Integer, Integer> entry: entryList){
if (entry.getValue() == maxFrequence)
results.add(entry.getKey());
else break;
}
return results.stream().mapToInt(i -> i).toArray();
}
}
方法二：基于二叉搜索树的特性¶
根据二叉搜索树的特性，中序遍历是有序的，因此可以相当于是在一个有序数组中求众数
可以先中序遍历得到有序数组，然后遍历一次数组得到最大的频率，再遍历一次数组得到所有的众数（因为众数不唯一，所以需要遍历两次）
直接在遍历二叉搜索树的过程中统计众数
也可以在 中序遍历的过程中直接统计，这个时候需要记录前一个节点，判断当前节点和前一个节点是否相等，如果相等，则频率加1（cnt）；
将当前节点的频率重新设置为1 (cntFrequence = 1)
因此可以先中序遍历一遍树，得到最大频率；然后再遍历一遍树，将频率等于最大频率的数字加入到resultList中
也可以判断当前频率 和 maxFrequence 的大小，如果和 maxFrequence 相等，直接将 当前节点对应的值 加入到 resultList 中 (但是需要注意，此时的maxFrequence不一定是最大的)；
因此当 当前的频率比 maxFrequence 大的时候，需要清空 resultList ，并将该数字加入到 resultList 中
两次遍历二叉树
class Solution {
// 直接基于二叉树的特性
// 记录最大的频率
int maxFrequence = 1;
// 记录当前数字的频率
int cntFrequence = 0;
// 记录前一个节点
TreeNode pre = null;
// 记录最终结果
List<Integer> resList = new ArrayList<>();
// 进行中序遍历 得到最大频率
public void traversal1(TreeNode cur){
if (cur == null) return;
traversal1(cur.left);
// 当前一个节点为null, 表示当前是第一个节点
if (pre == null) cntFrequence = 1;
else if (pre.val == cur.val) cntFrequence += 1;
else if (pre.val != cur.val) {
cntFrequence = 1;
}
// 注意：max更多是操作当前节点
maxFrequence = Math.max(maxFrequence, cntFrequence);
pre = cur;
traversal1(cur.right);
}
// 进行中序遍历 得到频率等于最大频率的数字
public void traversal2(TreeNode cur){
if (cur == null) return;
traversal2(cur.left);
// 当前一个节点为null, 表示当前是第一个节点
if (pre == null) cntFrequence = 1;
else if (pre.val == cur.val) cntFrequence += 1;
else if (pre.val != cur.val) {
cntFrequence = 1;
}
if (cntFrequence == maxFrequence){
resList.add(cur.val);
}
pre = cur;
traversal2(cur.right);
}
public int[] findMode(TreeNode root) {
if (root == null) return resList.stream().mapToInt(i->i).toArray();
// 中序遍历二叉树, 得到最大的频率
traversal1(root);
// 需要进行重新设置
pre = null;
cntFrequence = 0;
// 再次遍历二叉树, 得到等于最大频率的数字
traversal2(root);
return resList.stream().mapToInt(i->i).toArray();
}
}
一次遍历二叉树
class Solution {
// 直接基于二叉树的特性
// 记录最大的频率
int maxFrequence = 1;
// 记录当前数字的频率
int cntFrequence = 0;
// 记录前一个节点
TreeNode pre = null;
// 记录最终结果
List<Integer> resList = new ArrayList<>();
// 进行中序遍历 得到最大频率
public void traversal(TreeNode cur){
if (cur == null) return;
traversal(cur.left);
// 首先判断当前节点是否是第一个节点
if (pre == null) {
// pre == null 说明当前节点是第一个节点
// 设置当前节点的频率
cntFrequence = 1;
}
// 如果当前节点不是第一个节点
// 需要判断当前节点是否和前一个节点的数值相等
else if(cur.val == pre.val){
// 如果相等
// 当前节点频率加一
cntFrequence++;
}
else if (cur.val != pre.val){
// 如果不想等
// 说明当前节点的数值的新的数字
// 当前节点的频率设置为1
cntFrequence = 1;
}
// 判断当前节点的频率
if (cntFrequence == maxFrequence){
// 如果当前节点的频率 等于 最大频率
// 将当前节点对应数值加入到结果集中
resList.add(cur.val);
}
else if (cntFrequence > maxFrequence){
// 如果当前节点的频率 大于 最大频率
// 清空结果集, 并把当前节点加入
resList.clear();
resList.add(cur.val);
// 并更新最大频率
maxFrequence = cntFrequence;
}
// 开始下一个节点, 记录当前节点
pre = cur;
traversal(cur.right);
}
public int[] findMode(TreeNode root) {
// 需要注意, 是对当前节点进行操作
traversal(root);
return resList.stream().mapToInt(i->i).toArray();
}
}
22.二叉树的最近公共祖先¶
来源：LeetCode 236
最近公共祖先：对于一个树的两个节点 p、q，存在一个节点x，x是p、q的祖先并且x的深度尽可能大（一个节点也可以是它自己的祖先）
方法一：¶
思路：
寻找两个节点的最近公共祖先，需要从下向上遍历，因此应该使用后序遍历（左右中）的方法
寻找两个节点的最近公共祖先，会出现两种情况：
- 情况一：左子树出现节点p，右子树出现节点q（或者左子树出现节点q，右子树出现节点p）
- 情况二：节点本身是p，它有一个子孙节点q（或者节点本身是q，它有一个子孙节点p）
因此判断逻辑为： 1. 如果递归的过程中遇到p，就将p返回；如果递归的过程中遇到q，就将q返回。 2. 如果左右子树的返回值都不为空，说明此时中间的节点，一定是p和q的公共祖先
递归三部曲的确定：
-
确定递归函数返回值和传入的参数 递归中遇到p，将p返回；遇到q，将q返回 因为这都回的过程中要判断是否有p和q，因此需要将p和q传入
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q); -
确定终止条件 当遇到空节点，终止； 当遇到p或q，也终止
//即使root是p，子节点是q也直接返回;
// 因为题目中设定了只有一个p和q，在这种情况下虽然没有能够遍历到q，但是此时root就是最近的公共祖先，会通过一步步向上返回进行确定；
// 其他的分支在进行遍历的过程中返回的只会是null
if (root == p || root == q || root == null) return root;
- 确定单层循环的逻辑 因为需要搜索整个树，所以需要接收到返回值，并对返回值进行处理
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 对返回值进行处理
// 如果left 和 right 都不为空, 说明当前根节点是最近公共祖先
if (left != null && right != null ) return root;
// 如果 left 不为空, right为空，返回left (说明目标节点是通过left返回的)
if (left != null && right == null) return left;
// 如果 left 为空，right不为空，返回right(说明目标节点是通过right返回的)
if (left == null && right != null) return right;
if (left == null && right == null) return null;
代码：
class Solution {
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 root;
else if (left != null && right == null) return left;
else if (left == null && right != null) return right;
else return null;
}
}
方法二：¶
我们递归遍历整棵二叉树，定义 \(f_x\) 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：
\[
(f_{lson} \&\& f_{rson} ) || ( (x == p || x == q) || \&\& (f_{lson} || f_{rson}))
\]
其中 lson 代表 x 节点的左孩子， rson 代表 x 节点的有孩子。
\(f_{lson} \&\& f_{rson}\) ：左子树和右子树均 包含 p 节点或q节点 （满足这个条件, 说明 x就是最近公共祖先）
\(( (x == p || x == q) || \&\& (f_{lson} || f_{rson}))\) : x 本身是 p，其左子树或右子树包含q（或者x本身是q，其左子树或右子树包含p），此时x就是最近公共祖先
代码：
class Solution {
// 记录最近公共祖先
TreeNode ans = null;
// 进行后序遍历
public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
if (root == null) return false;
boolean left = dfs(root.left, p, q);
boolean right = dfs(root.right, p, q);
// 判断当前root是否是最近公共祖先
if ( (left && right) || ((root.val==p.val || root.val==q.val) && (left || right) ) ) ans = root;
// root并不是最近公共祖先
return (left || right) || root.val == p.val || root.val == q.val;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
}
23. 二叉搜索树的最近公共祖先¶
思路：
和上一题相比，二叉搜索树是有序的，因此最好能够使用二叉搜索树的特性。
如果某个节点是 节点p 和 节点q 的公共祖先，那么 该节点 一定在 \([p, q]\) 区间内；
因此只需要从上向下遍历，遇到这 \([p, q]\) 区间内的节点, 那么该节点就有一定是 节点p 和 节点q 的公共祖先，并且是最近公共祖先
递归三部曲
-
确定参数和返回值 需要返回最近公共祖先
TreeNode traversal(TreeNode root, TreeNode p, TreeNode q); -
确定终止条件
if (root == null) return root;
- 确定单层循环逻辑
// 正好在区间内, 直接返回
if ((root.val >= p.val && root.val <= q.val) || (root.val >= q.val && root.val <= p.val)) return root;
// 如果根节点比 p 和 q都大, 根据二叉搜索树的特性，遍历左边分支
if (root.val > p.val && root.val > q.val)
TreeNode left = traversal(root.left, p, q);
// 如果left 不为空, 说明已经找到, 直接返回
if (left != null) return left;
if (root.val > p.val && root.val > q.val)
TreeNode right = traversal(root.right, p, q);
if (right != null) return right;
代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 根据二叉搜索树的特性
if (root == null) return root;
if (root.val > p.val && root.val > q.val){
TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left != null) return left;
}
if (root.val < p.val && root.val < q.val){
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (right != null) return right;
}
// 当 root 正好在区间内
return root;
}
}
24. 二叉搜索树中的插入操作¶
思路：
二叉搜索树是有序树，因此只需要一步步遍历到 叶子节点，在叶子节点处添加就行
递归三部曲：
- 确定参数和返回值 通过返回值完成 新加入的节点与其父节点的插入操作
- 确定终止条件
if (root == null){ root = new TreeNode(val); return root; } - 单层循环逻辑
下一层将加入节点返回，本层用root->left或者root->right将其接住。
// 单层循环逻辑
if (val < root.val) root.left = insertIntoBST(root.left, val);
if (val > root.val) root.right = insertIntoBST(root.right, val);
return root;
代码：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
// 确定终止条件
if (root == null) {
root = new TreeNode(val);
}
// 单层循环逻辑
if (val < root.val) root.left = insertIntoBST(root.left, val);
if (val > root.val) root.right = insertIntoBST(root.right, val);
return root;
}
}
25. 删除二叉搜索树中的节点¶
来源：LeetCode 450
思路： 递归三部曲
- 确定参数和返回值
需要通过返回值 删除节点（和加入节点类似），一步步向上返回，最终返回根节点
TreeNode* deleteNode(TreeNode* root, int key) - 确定终止条件
遇到空返回，说明树中没有对应的节点
if (root == null) return root; - 确定单层循环的逻辑
// 单层循环逻辑 if (key < root.val) root.left = deleteNode(root.left, key); if (key > root.val) root.right = deleteNode(root.right, key); // 下面将会是 root.val = key的情况 if (key == root.val){ // 情况1：左右子节点都为空 if (root.left == null && root.right == null){ root = null; } // 情况2: 左孩子节点不为空,右孩子节点为空 else if(root.left != null && root.right == null){ root = root.left; } // 情况3: 左孩子节点为空, 右孩子节点不为空 else if (root.left == null && root.right != null){ root = root.right; } // 情况4: 左右孩子节点都不为空 // 这种情况下有两种选择 // (1) 将右孩子节点放入左孩子节点的最右边的 叶子节点下 // (2) 将左孩子节点放入右孩子节点的最左边的 叶子节点下 else if (root.left != null && root.right != null){ // 实现第一种选择, 寻找左孩子节点的最右边的叶子节点 TreeNode temp = root.left; while(temp.right != null) temp = temp.right; temp.right = root.right; root=root.left; } } return root;
代码：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
// 终止条件
if (root == null) return root;
// 单层循环逻辑
if (key < root.val) root.left = deleteNode(root.left, key);
if (key > root.val) root.right = deleteNode(root.right, key);
// 下面将会是 root.val = key的情况
if (key == root.val){
// 情况1：左右子节点都为空
if (root.left == null && root.right == null){
root = null;
}
// 情况2: 左孩子节点不为空,右孩子节点为空
else if(root.left != null && root.right == null){
root = root.left;
}
// 情况3: 左孩子节点为空, 右孩子节点不为空
else if (root.left == null && root.right != null){
root = root.right;
}
// 情况4: 左右孩子节点都不为空
// 这种情况下有两种选择
// (1) 将右孩子节点放入左孩子节点的最右边的 叶子节点下
// (2) 将左孩子节点放入右孩子节点的最左边的 叶子节点下
else if (root.left != null && root.right != null){
// 实现第一种选择, 寻找左孩子节点的最右边的叶子节点
TreeNode temp = root.left;
while(temp.right != null) temp = temp.right;
temp.right = root.right;
root=root.left;
}
}
return root;
}
}
26. 修剪二叉树¶
来源：LeetCode 669
思路：
因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。
但是有返回值，更方便，可以通过递归函数的返回值来移除节点。
递归三部曲：
1.确定参数和返回值 参照 插入元素 和 删除元素
TreeNode trimBST(TreeNode root, int low, int high);
if (root == null) return;
// 进行判断, 首先进行极限分析
// 情况1：如果 low 大于当前节点, 说明该节点及其左子树都不符合要求, 因此需要返回对其右子树进行修剪后的结果
if (low > root.val) {
TreeNode rightNode = trimBST(root.right, low, high);
return rightNode;
}
// 情况2: 如果 high 小于当前节点, 说明该节点及其右子树都不符合要求, 因此需要返回对其左子树进行修剪后的结果过
else if (high < root.val){
TreeNode leftNode = trimBST(root.left, low, high);
return leftNode;
}
// 情况3: 如果当前节点正好位于 [low, high] 的区间内, 那么分别对其左子树和右子树进行处理
// 并且将左节点 设置为 对左子树 修剪后的结果, 右节点设置为 对右子树 修剪后的结果
else {
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
代码：
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
// 终止条件
if (root == null) return root;
// 进行判断, 首先进行极限分析
// 情况1：如果 low 大于当前节点, 说明该节点及其左子树都不符合要求, 因此需要返回对其右子树进行修剪后的结果
if (low > root.val) {
TreeNode rightNode = trimBST(root.right, low, high);
return rightNode;
}
// 情况2: 如果 high 小于当前节点, 说明该节点及其右子树都不符合要求, 因此需要返回对其左子树进行修剪后的结果过
else if (high < root.val){
TreeNode leftNode = trimBST(root.left, low, high);
return leftNode;
}
// 情况3: 如果当前节点正好位于 [low, high] 的区间内, 那么分别对其左子树和右子树进行处理
// 并且将左节点 设置为 对左子树 修剪后的结果, 右节点设置为 对右子树 修剪后的结果
else {
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
}
27. 将有序数组转换为平衡二叉搜索树¶
来源：LeetCode 108
思路： 二叉搜索树的 中序遍历即 是一个有序数组，因此根据二叉搜索树的特性， 根据有序数组构造二叉搜索树，本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
递归三部曲： 1. 确定参数和返回值 参数：有序数组，区间索引 left right 返回值：需要通过返回值构造中间节点的 左孩子节点 和 右孩子节点
TreeNode traversal(int[] nums, int left, int right);
-
确定终止条件 因为是左闭右闭，因此当 left > right, 返回 null
-
单层循环逻辑
// 获得分割点 为了避免 爆 int
int mid = left + ((right - left ) / 2);
TreeNode root = new TreeNode(nums[mid]);
// 左边区间 左子树
root.left = traversal(nums, left, mid-1);
// 右边区间 右子树
root.right = traversal(nums, mid+1, right);
return root;
代码：
class Solution {
public TreeNode traversal(int[] nums, int left, int right){
// 设置终止条件 左闭右闭
if (left > right) return null;
// 获得分割点 为了避免 爆 int
int mid = left + ((right - left ) / 2);
TreeNode root = new TreeNode(nums[mid]);
// 左边区间 左子树
root.left = traversal(nums, left, mid-1);
// 右边区间 右子树
root.right = traversal(nums, mid+1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) return null;
return traversal(nums, 0, nums.length-1);
}
}
28. 把二叉搜索树转换为累加树¶
来源：LeetCode 538
题目解释：
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
换句话说，即将每一个节点的值修改为 原来的节点值 加上所有大于他的节点值之和。 因为中序遍历是从小到大，所以可以反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。
代码：
class Solution {
// 使用 sum 记录 前面所有比较大的数值的和
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null) return null;
// 右 中 左 反中序遍历
convertBST(root.right);
int temp = root.val;
root.val += sum;
sum += temp;
convertBST(root.left);
return root;
}
}