二叉树的递归遍历(前-中-后序)
// 前序遍历·递归·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); // 注意这一句
}
}二叉树的层次遍历(?BFS--迭代方式--借助队列)
//BFS--迭代方式--借助队列
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun(root);
return resList;
}
//BFS--迭代方式--借助队列
public void checkFun(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}给你一棵二叉树的根节点?root?，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
//DFS--递归
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return root;
TreeNode left=invertTree(root.left);
TreeNode right=invertTree(root.right);
swap(root);
return root;
}
//交换
public void swap(TreeNode root){
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
//BFS--层次遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node = queue.poll();
swap(node);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return root;
}
public void swap(TreeNode root){
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}给你一个二叉树的根节点?root?， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
//DFS--递归
class Solution {
public boolean isSymmetric(TreeNode root) {
return compare(root.left,root.right);
}
public boolean compare(TreeNode left,TreeNode right){
if(left==null&&right!=null) return false;
if(right==null&&left!=null) return false;
if(left==null&&right==null) return true;
if(left.val!=right.val) return false;
return compare(left.left,right.right)&&compare(left.right,right.left);
}
}
//BFS--层次 队列
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode left=queue.poll();
TreeNode right=queue.poll();
if(left==null&&right!=null) return false;
if(left!=null&&right==null) return false;
if(left==null&&right==null) continue;
if(left.val!=right.val) return false;
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
}
return true;
}
}
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
//递归
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int res=0;
int leftDepth=minDepth(root.left);
int rightDepth=minDepth(root.right);
if(root.left==null&&root.right!=null){
return rightDepth+1;
}
if(root.left!=null&&root.right==null){
return leftDepth+1;
}
res=Math.min(leftDepth,rightDepth)+1;
return res;
}
}
//BFS 队列
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int depth=0;
while(!queue.isEmpty()){
int size=queue.size();
depth++;
while(size-->0){
TreeNode node=queue.poll();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
if(node.left==null&&node.right==null) return depth;
}
}
return depth;
}
}给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~?2h?个节点。
//递归
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
int res=0;
if(root.left!=null){
res+=countNodes(root.left);
}
if(root.right!=null){
res+=countNodes(root.right);
}
return res+1;
}
}
//BFS
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int res=0;
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node=queue.poll();
res++;
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return res;
}
}示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点?的左右两个子树的高度差的绝对值不超过 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
//递归
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int left=hight(root.left);
int right=hight(root.right);
if(Math.abs(right-left)>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
//递归求高度
public int hight(TreeNode root){
if(root==null) return 0;
return Math.max(hight(root.left),hight(root.right))+1;
}
}
//BFS求高度
public int hight(TreeNode root){
if(root==null) return 0;
Queue<TreeNode> node = new LinkedList<>();
queue.offer(root);
int res=0;
while(!queue.isEmpty()){
int size=queue.size();
res++;
while(size-->0){
TreeNode node=queue.poll();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return res;
}给你一个二叉树的根节点?root?，按?任意顺序?，返回所有从根节点到叶子节点的路径。
叶子节点?是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res=new LinkedList<>();
List<Integer> path=new LinkedList<>();
getPath(root,res,path);
return res;
}
public void getPath(TreeNode root,List<String> res,List<Integer> path){
if(root==null) return;
path.add(root.val);
if(root.left==null&&root.right==null){//叶子节点
StringBuilder sb=new StringBuilder();
for(int i=0;i<path.size()-1;i++){
sb.append(path.get(i)).append("->");
}
sb.append(path.get(path.size()-1));//处理最后一个节点
res.add(sb.toString());
}
if(root.left!=null){
getPath(root.left,res,path);
path.remove(path.size()-1);
}
if(root.right!=null){
getPath(root.right,res,path);
path.remove(path.size()-1);
}
}
}给定二叉树的根节点?root?，返回所有左叶子之和。
示例 1：
转存失败重新上传取消
输入: root = [3,9,20,null,null,15,7]?
输出: 24?
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例?2:
输入: root = [1] 输出: 0
//DFS 递归
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
int left=sumOfLeftLeaves(root.left);
int right=sumOfLeftLeaves(root.right);
int value=0;
if(root.left!=null&&root.left.left==null&&root.left.right==null){
value+=root.left.val;
}
int res=left+right+value;
return res;
}
}
//BFS 层次 队列
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null || root.left==null&&root.right==null) return 0;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int sum=0;
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node=queue.poll();
if(node.left!=null) {
if(node.left.left==null&&node.left.right==null){
sum+=node.left.val;
}
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
}
return sum;
}
}
这题在层次遍历中出错，直接在node.left!=null里面判断是左叶子就行?
这题关键点是：1.找左叶子 2.左叶子的判断是root.left!=null&&root.left.left==null&&root.left.right==null
给定一个二叉树的?根节点?root，请找出该二叉树的?最底层?最左边?节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
// 递归法
class Solution {
private int Deep = -1;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root,0);
return value;
}
private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {//到叶子节点
if (deep > Deep) {
value = root.val;
Deep = deep;//到最大深度
}
}
findLeftValue(root.left,deep + 1);
findLeftValue(root.right,deep + 1);
}
}
//BFS 层次
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root==null) return 0;
if(root.left==null&&root.right==null) return root.val;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int res=0;
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node=queue.poll();
if(size==0) res=node.val;
if(node.right!=null) {
queue.offer(node.right);
}
if(node.left!=null) {
queue.offer(node.left);
}
}
}
return res;
}
}本题递归需要注意的是：1 先找叶子节点 2 找最大深度? 层次遍历只需要每次更新size=0即最左边的节点的值
给你二叉树的根节点?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
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
targetSum-=root.val;
if(root.left==null&&root.right==null&&targetSum==0) return true;
if(root.left!=null) {
if(hasPathSum(root.left,targetSum))
return true;
}
if(root.right!=null){
if(hasPathSum(root.right,targetSum))
return true;
}
return false;
}
}class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0 || postorder.length==0) return null;
return build(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode build(int[] inorder,int inorderLeft,int inorderRight,int[] postorder,int posLeft,int posRight){
int rootValue=postorder[postRight-1];//找到后序节点的尾节点 该节点为原树的头节点
TreeNode root=new TreeNode(rootValue);//构造头节点
int rootIndex=0;
for(int i=inorderLeft;i<inorderRight;i++){//在中序中找到分割点
if(rootValue==inorder[i]){
rootIndex=i;
break;
}
}
//递归
root.left=build(inorder,inorderLeft,rootInex,postorder,posLeft,posLeft+(rootIndex-inorderLeft));
root.right=build(inorder,rootIndex+1,inorderRight,postorder,posLeft+(rootIndex-1),posRight);
}
}给定一个不重复的整数数组?nums 。?最大二叉树?可以用下面的算法从?nums 递归地构建:
创建一个根节点，其值为?nums 中的最大值。
递归地在最大值?左边?的?子数组前缀上?构建左子树。
递归地在最大值 右边 的?子数组后缀上?构建右子树。
返回?nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
? ? - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
? ? ? ? - 空数组，无子节点。
? ? ? ? - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
? ? ? ? ? ? - 空数组，无子节点。
? ? ? ? ? ? - 只有一个元素，所以子节点是一个值为 1 的节点。
? ? - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
? ? ? ? - 只有一个元素，所以子节点是一个值为 0 的节点。
? ? ? ? - 空数组，无子节点。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length==0) return null;
return build(nums,0,nums.length);
}
public TreeNode build(int[] nums,int left,int right){
if(right-left<1) return null;
if(right-left==1) return new TreeNode(nums[left]);
int rootValue=0;
int rootIndex=0;
for(int i=0;i<nums.length;i++){
if(nums[i]>rootValue){
rootValue=nums[i];
rootIndex=i;
}
}
TreeNode root=new TreeNode(rootValue);
root.left=build(nums,left,rootIndex);
root.right=build(nums,rootIndex+1,right);
return root;
}
}给你两棵二叉树： 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]
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null&&root2==null) return null;
if(root1==null&&root2!=null) return root2;//root2不为空 返回root2
if(root1!=null&&root2==null) return root1;//root1不为空 返回root2
TreeNode root=new TreeNode(root1.val+root2.val);//创建新的节点
root.left=mergeTrees(root1.left,root2.left);//合并左节点
root.right=mergeTrees(root1.right,root2.right);//合并右节点
return root;
}
}给定二叉搜索树（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 输出：[]
//利用二叉搜索树的性质
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null) return null;
if(root.val==val) return root;
if(val<root.val){
return searchBST(root.left,val);
}else if(val>root.val){
return searchBST(root.right,val);
}
return root;
}
}给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
class Solution {
public boolean isValidBST(TreeNode root) {
return isBST(root,null,null);
}
public boolean isBST(TreeNode root,TreeNode min,TreeNode max){
if(root==null) return true;
if(min!=null&&root.val<=min.val) return false;
if(max!=null&&root.val>=max.val) return false;
return isBST(root.left,min,root)&&isBST(root.right,root,max);
}
}给你一个二叉搜索树的根节点?root?，返回?树中任意两不同节点值之间的最小差值?。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1?
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
注意：如果出现二叉搜索树求最值，差值之类的，把它转化成有序数组，然后中序遍历
class Solution {
TreeNode pre;
int res=Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root==null) return 0;
traval(root);
return res;
}
public void traval(TreeNode root){
if(root==null) return;
traval(root.left);
if(pre!=null){
res=Math.min(res,root.val-pre.val);
}
pre=root;
traval(root.right);
}
}给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。
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 null;
if(left==null && right!=null) return right;
if(left!=null && right==null) return left;
return root;
}
}给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 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, 因为根据定义最近公共祖先节点可以为节点本身。
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(root.val<p.val&&root.val<q.val) return left;
if(root.val>p.val&&root.val>q.val) return right;
return root;
}
}给定二叉搜索树（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]
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
if(root.val>val) root.left=insertIntoBST(root.left,val);
if(root.val<val) root.right=insertIntoBST(root.right,val);
return root;
}
}给定一个二叉搜索树的根节点 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
输出: []
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
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;
}
}给你二叉搜索树的根节点 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]
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null) return null;
if(root.val>low){
TreeNode left=trimBST(root.left,low,high);//寻找符合区间
return left;
}
if(root.val<high){
TreeNode right=trimBST(root.right,low,high);//寻找符合区间
return right;
}
root.left=trimBST(root.left,low,high);
root.right=trimBST(root.right,low,high);
return root;
}
}给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
?
?
输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0) return null;
return travel(nums,0,nums.length-1);
}
public TreeNode travel(int[] nums,int left,int right){
if(left>right) return null;
int mid=left+(right-left)/2;
TreeNode root=new TreeNode(nums[mid]);//构造头节点
root.left=travel(nums,left,mid-1);//构造左节点
root.right=travel(nums,mid+1,right);//构造右节点
return root;
}
}给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node?的新值等于原树中大于或等于?node.val?的值之和。
?
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
思路：采用中序遍历的逆序，也就是右中左的顺序
class Solution {
int pre=0;
public TreeNode convertBST(TreeNode root) {
return travel(root);
}
public TreeNode travel(TreeNode root){
if(root==null) null;
travel(root.right);//右
root.val+=pre;//中
pre=root.val;
travel(root.left);//左
return root;
}
}?
?
?