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) {//31-37if(nums.length==0) return null;int max = -1;int index = -1;for(int i=0;iif(nums[i]>max){max = nums[i];index = i;}}TreeNode root = new TreeNode(nums[index]);root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,index));root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,index+1,nums.length));return root;}
}

501 二叉搜索树的众数

写了非常非常久！！因为搜索树遍历的时候就是按顺序大小的，所以只要在中序遍历 本层递归的逻辑中记录出现次数最多的元素！！不用map

/*** 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 {ArrayList list = new ArrayList();ArrayList res = new ArrayList();int maxcount, count;int base;public int[] findMode(TreeNode root) {//45-23inorder(root);int[] re = new int[res.size()];for(int i=0;iif(root==null) return;inorder(root.left);//本层递归逻辑if(root.val==base){count++;}else{//因为是搜索树，遍历的元素一定是递增的 才能这么做count=1;base = root.val;} if(count==maxcount){res.add(base);}//要先判断等于，再判断大于，否则会元素重复，因为要把清空放后面if(count>maxcount){res.clear();res.add(base);maxcount = count;}inorder(root.right);}
}

236 二叉树的最近公共祖先

从下往上找，后序遍历就是从下网上，在后序遍历的处理本层逻辑中返回。
如何从底向上遍历？
遍历整棵树，还是遍历局部树？
如何把结果传到根节点的？
遍历整个树就要开两个变量把左右节点都接住

/*** 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) {//16 后序遍历-20//递归结束条件if(root==null||root==p||root==q) return root;//后序遍历TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);//本层处理逻辑if(left==null&&right==null) return null;//左子树空返回右子树，反之亦然else if(left==null&&right!=null) return right;else if(left!=null&&right==null) return left;//两边都不空，说明当前就是公共祖先else return root;}
}

701 二叉搜索树的插入操作

很简单但是写了很久！！

/*** 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 insertIntoBST(TreeNode root, int val) {if(root==null) return new TreeNode(val);TreeNode res = root;while(root.left!=null||root.right!=null){if(root.valif(root.right==null){root.right = new TreeNode(val);return res;}root = root.right;}else if(root.val>val){if(root.left==null&&root.val>val){root.left = new TreeNode(val);return res;}root = root.left;}}if(root.left==null&&root.val>val){root.left = new TreeNode(val);return res;}else if(root.right==null&&root.valroot.right = new TreeNode(val);return res;}return res;}
}

450 删除二叉搜索树中的节点

要调整二叉树的结构，感觉非常难，特别是当要删除的节点的左右节点都不为空的情况下，一直往平衡二叉树的左右旋中去想就更加复杂，其实只需要把要删除节点的左子树放到右子树的最左节点下就行
例如，要删除7，只要把7的左子树，放到8下就可以！！


然后再按照左子树空右子树不空的情况

/*** 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) {//14if(root==null) return null;if(root.val//要把左右子树接住root.right = deleteNode(root.right,key);}else if(root.val>key){root.left = deleteNode(root.left,key);}else if(root.val==key){//刚好是叶子节点，返回空if(root.left==null&&root.right==null) return null;//左子树空右子树不空 返回左子树else if(root.left==null&&root.right!=null) return root.right;//左子树不空右子树空 返回左子树else if(root.left!=null&&root.right==null) return root.left;//都不为空else if(root.left!=null&&root.right!=null){TreeNode node = root.right;while(node.left!=null) node = node.left;//把左子树放到右子树的最左节点下边node.left = root.left;return root.right;}}return root;}
}

669. 修剪二叉搜索树

/*** 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.valhigh) return trimBST(root.left,low,high);//返回的接住root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);      return root;}}

直接用递归写不太容易想到，还是要练习

108. 将有序数组转换为二叉搜索树

/*** 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 sortedArrayToBST(int[] nums) {//00 左闭右开return makeTree(nums,0,nums.length);      }public TreeNode makeTree(int nums[], int begin, int end){if(end<=begin) return null;if(end - begin==1) return new TreeNode(nums[begin]);else{int mid = begin+(end-begin)/2;TreeNode root = new TreeNode(nums[mid]);root.left = makeTree(nums,begin,mid);root.right = makeTree(nums,mid+1,end);return root;}        }
}

538. 把二叉搜索树转换为累加树

换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，感觉这就简单了。知道如何遍历这个二叉树，就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。!!!

/*** 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 sum;public TreeNode convertBST(TreeNode root) {af(root);return root;}public void af(TreeNode root){if(root==null) return;af(root.right);sum+=root.val;root.val = sum;af(root.left);}
}