class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums,0,nums.length);
}
public TreeNode construct(int [] nums,int l,int r){
if(r-l<1){
return null;
}
if(r-l==1){
return new TreeNode(nums[l]);
}
int maxNum=-1;
int index =l;
for(int i = l;i<r;i++){
if(nums[i]>maxNum){
maxNum=nums[i];
index=i;
}
}
TreeNode node = new TreeNode(maxNum);
node.left = construct(nums,l,index);
node.right = construct(nums,index+1,r);
return node;
}
}体会一下递归操作两棵二叉树。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
root1.val+=root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}二叉搜索树特点：
左孩子小于根节点，右孩子大于根节点
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null || root.val==val){
return root;
}
TreeNode left = searchBST(root.left,val);
TreeNode right = searchBST(root.right,val);
if(left!=null) return left;
return right;
}
}根据特点优化
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null || root.val==val){
return root;
}
if(val<root.val){
return searchBST(root.left,val);
}else{
return searchBST(root.right,val);
}
}
}利用BST特点迭代，不需要栈
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root!=null){
if(val<root.val) root = root.left;
else if(val>root.val) root = root.right;
else return root;
}
return null;
}
}遇到?搜索树，一定想着中序遍历，这样才能利用上特性。?
但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。
就是不能单纯的比较root》left? root<right，比较的时候可以采用指针的方式，注意指针定义到递归外面，整体判断是先判断左孩子和根节点是true，再判断根节点和有孩子是true，都为true这个树才是true。做递归题的时候，先按照单层逻辑写下来再看整体的具体递归的逻辑，方便思考，不然会一入递归深似海啊~
class Solution {
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
if(root==null)return true;
boolean left = isValidBST(root.left);
if(pre!=null&&pre.val>=root.val){
return false;
}
pre = root;
boolean right = isValidBST(root.right);
return left&&right;
}
}