二叉树
递归前中后徐遍历
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(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);
}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); // 注意这一句
inorder(root.right, list);
}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); // 注意这一句
}
}
迭代前中后序遍历
解答
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
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 node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
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;
}
}
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
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 node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
102 二叉树的层序遍历
相似题目
学会二叉树的层序遍历，可以一口气打完以下十题：
- 102.二叉树的层序遍历
- 107.二叉树的层次遍历II
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429.N叉树的层序遍历
- 515.在每个树行中找最大值
- 116.填充每个节点的下一个右侧节点指针
- 117.填充每个节点的下一个右侧节点指针II
- 104.二叉树的最大深度
- 111.二叉树的最小深度
102. 二叉树的层序遍历
难度中等1388收藏分享切换为英文接收动态反馈
给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]
解答
/**
* 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>> levelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null){
return res;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=deque.size();
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
list.add(node.val);
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
res.add(list);
}
return res;
}
}
107 二叉树的层序遍历②
107. 二叉树的层序遍历 II
难度中等594收藏分享切换为英文接收动态反馈
给你二叉树的根节点
root，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000
解答
//最终把数组反转一下可以了
/**
* 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) {
LinkedList<List<Integer>> list=new LinkedList<>();
if(root==null){
return list;
}
Queue<TreeNode> que=new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len=que.size();
List<Integer> res=new LinkedList<>();
for(int i=1;i<=len;i++){
TreeNode node=que.poll();
res.add(node.val);
if(node.left!=null){
que.offer(node.left);
}
if(node.right!=null){
que.offer(node.right);
}
}
list.addFirst(res);
}
return list;
}
}
199 二叉树的右视图
199. 二叉树的右视图
难度中等723收藏分享切换为英文接收动态反馈
给定一个二叉树的 根节点
root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]示例 2:
输入: [1,null,3] 输出: [1,3]示例 3:
输入: [] 输出: []提示:
- 二叉树的节点个数的范围是
[0,100]-100 <= Node.val <= 100
解答
注意事项：size问题 要事先得到每层的size 不要用deque.size() 因为for循环中deque.size()是不断变化的
/**
* 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> rightSideView(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null){
return res;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
//size这里不要用deque.size() 因为他是不断变化的
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
if(i==size-1){
res.add(node.val);
}
}
}
return res;
}
}
637 二叉树的层平均值
637. 二叉树的层平均值
难度简单358收藏分享切换为英文接收动态反馈
给定一个非空二叉树的根节点
root, 以数组的形式返回每一层节点的平均值。与实际答案相差10-5以内的答案可以被接受。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
解答
/**
* 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<Double> averageOfLevels(TreeNode root) {
List<Double> res=new ArrayList<>();
if(root==null){
return res;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
double temp=0;
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
temp+=node.val;
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
res.add(temp/size);
}
return res;
}
}
515 在每个树行中找最大值
515. 在每个树行中找最大值
难度中等260收藏分享切换为英文接收动态反馈
给定一棵二叉树的根节点
root，请找出该二叉树中每一层的最大值。示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]示例2：
输入: root = [1,2,3] 输出: [1,3]提示：
- 二叉树的节点个数的范围是
[0,104]-231 <= Node.val <= 231 - 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<Integer> largestValues(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null){
return res;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
int temp=Integer.MIN_VALUE;
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
temp=Math.max(temp,node.val);
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
res.add(temp);
}
return res;
}
}
429 N叉树的层序遍历
429. N 叉树的层序遍历
难度中等300收藏分享切换为英文接收动态反馈
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示：
- 树的高度不会超过
1000- 树的节点总数在
[0, 10^4]之间
解答
/*
// 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) {
List<List<Integer>> list=new ArrayList<>();
if(root==null){
return list;
}
Queue<Node> que=new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len=que.size();
List<Integer> res=new LinkedList<>();
for(int i=1;i<=len;i++){
Node node=que.poll();
res.add(node.val);
if(node.children!=null){
List<Node> children=node.children;
for(Node temp:children){
que.offer(temp);
}
}
}
list.add(res);
}
return list;
}
}
104 二叉树的最大深度
104. 二叉树的最大深度
难度简单1293收藏分享切换为英文接收动态反馈
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树[3,9,20,null,null,15,7]，3 / \ 9 20 / \ 15 7返回它的最大深度 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 int maxDepth(TreeNode root) {
int res=0;
if(root==null){
return 0;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
res++;
}
return res;
}
}
递归
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return Math.max(left,right)+1;
}
}
111 二叉树的最小深度
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
解答
/**
* 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 minDepth(TreeNode root) {
int res=0;
if(root==null){
return 0;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
res++;
while(!deque.isEmpty()){
int size=deque.size();
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
if(node.left==null && node.right==null){
return res;
}
}
res++;
}
return res;
}
}
递归
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
int left=minDepth(root.left);
int right=minDepth(root.right);
//注意这里
if(root.left==null){
return right+1;
}
//注意这里
if(root.right==null){
return left+1;
}
return Math.min(left,right)+1;
}
}
116 填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针
难度中等830收藏分享切换为英文接收动态反馈
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。示例 1：
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2:
输入：root = [] 输出：[]
解答
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null){
return null;
}
Deque<Node> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
for(int i=0;i<size;i++){
Node node=deque.poll();
if(i<size-1){
node.next=deque.peek();
}
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
}
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II
难度中等606收藏分享切换为英文接收动态反馈
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
解答
与上一题代码一样
101 对称二叉树
101. 对称二叉树
难度简单2007收藏分享切换为英文接收动态反馈
给你一个二叉树的根节点
root， 检查它是否轴对称。示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false提示：
- 树中节点数目在范围
[1, 1000]内-100 <= Node.val <= 100
解答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 boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return check(root.left,root.right);
}
public boolean check(TreeNode left,TreeNode right){
if(left == null && right ==null){
return true;
}
if(left == null || right ==null){
return false;
}
if(left.val != right.val){
return false;
}
return left.val==right.val && check(left.right,right.left) && check(left.left,right.right);
}
}
解答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 boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while(!deque.isEmpty()){
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
}
257 二叉树的所有路径
257. 二叉树的所有路径
难度简单781收藏分享切换为英文接收动态反馈
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]示例 2：
输入：root = [1] 输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内-100 <= Node.val <= 100
解答
/**
* 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) {
List<String> res=new ArrayList<>();
if(root==null){
return res;
}
List<Integer> path=new ArrayList<>();
backTrack(res,path,root);
return res;
}
public static void backTrack(List<String> res,List<Integer> path,TreeNode root){
path.add(root.val);
if(root.left==null && root.right==null){
StringBuilder str=new StringBuilder();
for(int i=0;i<path.size()-1;i++){
str.append(path.get(i)).append("->");
}
str.append(path.get(path.size()-1));
res.add(str.toString());
}
if(root.left!=null){
backTrack(res,path,root.left);
path.remove(path.size()-1);
}
if(root.right!=null){
backTrack(res,path,root.right);
path.remove(path.size()-1);
}
}
}
解答二 （迭代）
// 解法2
class Solution {
/**
* 迭代法
*/
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;
}
}
110 平衡二叉树 :negative_squared_cross_mark:
110. 平衡二叉树
难度简单1072
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false示例 3：
输入：root = [] 输出：true
解答
/**
* 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 boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
return Math.abs(getHeight(root.left) -getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public static int getHeight(TreeNode node){
if(node==null){
return 0;
}else{
return Math.max(getHeight(node.left),getHeight(node.right))+1;
}
}
}
404 左叶子之和
404. 左叶子之和
难度简单478
给定二叉树的根节点
root，返回所有左叶子之和。示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24示例 2:
输入: root = [1] 输出: 0提示:
- 节点数在
[1, 1000]范围内-1000 <= Node.val <= 1000
解答
/**
* 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;
}
int sum=0;
int left=sumOfLeftLeaves(root.left);
int right=sumOfLeftLeaves(root.right);
if(root.left!=null &&root.left.right==null&&root.left.left==null){
sum+=root.left.val;
}
return left+right+sum;
}
}
222 完全二叉树的节点个数
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点
root，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h层，则该层包含1~ 2h个节点。示例 1：
输入：root = [1,2,3,4,5,6] 输出：6示例 2：
输入：root = [] 输出：0示例 3：
输入：root = [1] 输出：1提示：
- 树中节点的数目范围是
[0, 5 * 104]0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
递归
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}
迭代
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
int res=0;
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
res++;
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
}
return res;
}
}
513 找树左下角的值
513. 找树左下角的值
难度中等356
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7提示:
- 二叉树的节点个数的范围是
[1,104]-231 <= Node.val <= 231 - 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 int findBottomLeftValue(TreeNode root) {
if(root==null){
return 0;
}
int res=0;
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
if(i==0){
res=node.val;
}
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
}
return res;
}
}
112 路径总和
112. 路径总和
难度简单943
给你二叉树的根节点
root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：
- 树中节点的数目在范围
[0, 5000]内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解答 迭代
/**
* 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;
* }
* }
*/
/*思路
建立两个队列 一个存放节点 一个存放 节点值
在循环中如果遍历到 叶子节点判断时候符合条件 不符合continue 符合直接返回true*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}
Queue<TreeNode> queNode=new LinkedList<>();
Queue<Integer> queVal=new LinkedList<>();
queNode.offer(root);
queVal.offer(root.val);
while(!queNode.isEmpty()){
TreeNode t=queNode.poll();
int temp=queVal.poll();
if(t.left==null && t.right==null){
if(temp==targetSum){
return true;
}
continue;
}
if(t.left!=null){
queNode.offer(t.left);
queVal.offer(t.left.val+temp);
}
if(t.right!=null){
queNode.offer(t.right);
queVal.offer(t.right.val+temp);
}
}
return false;
}
}
解答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 boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}
targetSum-=root.val;
if(root.left==null && root.right ==null){
return targetSum==0;
}
if(root.left!=null){
if(hasPathSum(root.left,targetSum)){
return true;
}
}
if(root.right!=null){
if(hasPathSum(root.right,targetSum)){
return true;
}
}
return false;
}
}
105 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
难度中等1661
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列\
代码
/**
* 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) {
if(preorder==null||preorder.length==0){
return null;
}
TreeNode root=new TreeNode(preorder[0]);
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
int inorderIndex=0;
for(int i=1;i<preorder.length;i++){
int preorderVal = preorder[i];
TreeNode node=stack.peek();
if(node.val!=inorder[inorderIndex]){
node.left=new TreeNode(preorder[i]);
stack.push(node.left);
}else{
while(!stack.isEmpty() && stack.peek().val==inorder[inorderIndex]){
node=stack.pop();
inorderIndex++;
}
node.right=new TreeNode(preorder[i]);
stack.push(node.right);
}
}
return root;
}
}
题解
106. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
难度中等795
给定两个整数数组
inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
解答
/**
* 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) {
if (postorder == null || postorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = inorder.length - 1;
for(int i=postorder.length - 2;i>=0;i--){
TreeNode node=stack.peek();
if(node.val!=inorder[inorderIndex]){
node.right=new TreeNode(postorder[i]);
stack.push(node.right);
}else{
while(!stack.isEmpty() && stack.peek().val==inorder[inorderIndex]){
node=stack.pop();
inorderIndex--;
}
node.left=new TreeNode(postorder[i]);
stack.push(node.left);
}
}
return root;
}
}
617 合并二叉树
617. 合并二叉树
难度简单1022
给你两棵二叉树：
root1和root2。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7]示例 2：
输入：root1 = [1], root2 = [1,2] 输出：[2,2]提示：
- 两棵树中的节点数目在范围
[0, 2000]内-104 <= Node.val <= 104
解答 递归
/**
* 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) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
root1.val=root1.val+root2.val;
root1.left=mergeTrees(root1.left,root2.left);
root1.right=mergeTrees(root1.right,root2.right);
return root1;
}
}
解答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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.offer(root1);
deque.offer(root2);
while(!deque.isEmpty()){
TreeNode node1=deque.poll();
TreeNode node2=deque.poll();
node1.val+=node2.val;
if(node1.left!= null && node2.left !=null){
deque.offer(node1.left);
deque.offer(node2.left);
}
if(node1.right!= null && node2.right !=null){
deque.offer(node1.right);
deque.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;
}
}
700 二叉搜索树中的搜索
700. 二叉搜索树中的搜索
难度简单304
给定二叉搜索树（BST）的根节点
root和一个整数值val。你需要在 BST 中找到节点值等于
val的节点。 返回以该节点为根的子树。 如果节点不存在，则返回null。示例 1:
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]示例 2:
输入：root = [4,2,7,1,3], val = 5 输出：[]提示：
- 数中节点数在
[1, 5000]范围内1 <= Node.val <= 107root是二叉搜索树1 <= val <= 107
解答：递归
/**
* 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 searchBST(TreeNode root, int val) {
if(root==null || root.val==val){
return root;
}
if(root.val>val){
return searchBST(root.left,val);
}
if(root.val<val){
return searchBST(root.right,val);
}
return null;
}
}
解答2 迭代
class Solution {
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;
}
}
98 验证二叉搜索树
98. 验证二叉搜索树
难度中等1671
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
List<Integer> list=new ArrayList<>();
isV(root,list);
for (int i = 0; i < list.size()-1;i++) {
if(list.get(i)<list.get(i+1)){
continue;
}else{
return false;
}
}
return true;
}
public List<Integer> isV(TreeNode root,List list){
if(root==null){
return list;
}
isV(root.left,list);
list.add(root.val);
isV(root.right,list);
return list;
}
}
530 二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点
root，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：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 int getMinimumDifference(TreeNode root) {
int x=Integer.MAX_VALUE;
List<Integer> res=new ArrayList<>();
midTravel(root,res);
int[] array = res.stream().mapToInt(Integer::intValue).toArray();
for(int i=0;i<array.length-1;i++){
int temp=array[i+1]-array[i];
if(x>temp){
x=temp;
}
}
return x;
}
public static void midTravel(TreeNode root,List<Integer> res){
if(root==null){
return;
}
midTravel(root.left,res);
res.add(root.val);
midTravel(root.right,res);
}
}
501 二叉搜索树中的众数
501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点
root，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]示例 2：
输入：root = [0] 输出：[0]提示：
- 树中节点的数目在范围
[1, 104]内-105 <= Node.val <= 105
解答
/**
* 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[] findMode(TreeNode root) {
HashMap<Integer,Integer> map=new HashMap<>();
List<Integer> res=new ArrayList<>();
if (root == null)
return res.stream().mapToInt(Integer::intValue).toArray();
midTravel(root,map);
List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
.collect(Collectors.toList());
res.add(mapList.get(0).getKey());
for(int i=1;i<mapList.size();i++){
if(mapList.get(i).getValue()==mapList.get(i-1).getValue()){
res.add(mapList.get(i).getKey());
}else{
break;
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
public static void midTravel(TreeNode root,HashMap<Integer,Integer> map){
if(root==null){
return;
}
midTravel(root.left,map);
map.put(root.val, map.getOrDefault(root.val, 0) + 1);
midTravel(root.right,map);
}
}
236 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
难度中等1851
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==p || root==q || root==null){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null){
return root;
}
if(left==null && right!=null){
return right;
}else if(left!=null && right==null){
return left;
}else{
return null;
}
}
}
236 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先
难度简单884
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
解答 1
与上方递归代码一样 效率很差 没用到二叉搜索树的特性
解答2 迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
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;
}
}
701 二叉搜索树的插入操作
701. 二叉搜索树中的插入操作
难度中等337
给定二叉搜索树（BST）的根节点
root和要插入树中的值value，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5] 解释：另一个满足题目要求可以通过的树是：示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]提示：
- 树中的节点数将在
[0, 104]的范围内。-108 <= Node.val <= 108- 所有值
Node.val是 独一无二 的。-108 <= val <= 108- 保证
val在原始BST中不存在。
解答 迭代
//用一个pre 记录上一个节点
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
return new TreeNode(val);
}
TreeNode newRoot = root;
TreeNode pre=root;
while(root!=null){
pre=root;
if(root.val>val){
root=root.left;
}else if(root.val<val){
root=root.right;
}
}
if(pre.val>val){
pre.left=new TreeNode(val);
}else{
pre.right=new TreeNode(val);
}
return newRoot;
}
}
450 删除二叉搜索树的节点
450. 删除二叉搜索树中的节点
难度中等910
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点示例 3:
输入: root = [], key = 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 TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val == key) {
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;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
}
669 修建二叉搜索树
669. 修剪二叉搜索树
难度中等579
给你二叉搜索树的根节点
root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,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 TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return null;
}
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
// root在[low,high]范围内
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
