654.最大二叉树
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
递归三步曲：
1、传入参数，整数数组，数组的开始和结束，返回树的中间节点。
2、终止条件：开始大于等于结束，即数组为空。
3、递归逻辑：找到最大的元素，记录元素其下标，构建中间节点；递归构造左子树和右子树。
代码如下：
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return buildTree(nums,0,nums.length);}public TreeNode buildTree(int[] nums,int start,int end){if(start>=end){return null;}int maxIndex=start;int maxNum=nums[maxIndex];for(int i=start;i<end;i++){if(nums[i]>maxNum){maxIndex=i;maxNum=nums[i];}}TreeNode root=new TreeNode(maxNum);root.left=buildTree(nums,start,maxIndex);root.right=buildTree(nums,maxIndex+1,end);return root;}
}
注意：递归函数中一定要使用受约束的start和end，不要随意写，不然容易出错。
617.合并二叉树
递归三部曲：
1、传入参数：两个树的中间节点root1和root2，返回新树的中间节点root；返回值类行为TreeNode；
2、终止条件：如果root1为空，return root2；如果root2为空，返回root1。
3、递归逻辑：两节点的值相加作为新节点的值。可以直接在树1上去构建，递归构建左树，递归构建右树。
代码如下：
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;}
}
700.二叉搜索树中的搜索
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
递归
直接选用先序遍历，找到节点之后直接return即可。
递归三部曲：
1、传入参数：根节点、目标值，返回目标节点。直接使用原函数即可。
2、终止条件：节点为空或找到当前节点则返回该节点
3、递归逻辑：如果当前节点的值小于val，搜索右子树；若当前节点的值大于val，搜索左子树。
代码如下：
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root==null || root.val==val) return root;if(root.val<val) return searchBST(root.right,val);else return searchBST(root.left,val);}
}
迭代
根据二叉搜索树的特性直接一路循环即可，无需栈或队列进行存储和回溯。
class Solution {public TreeNode searchBST(TreeNode root, int val) {TreeNode node=root;while(node!=null){if(node.val==val) return node;else if(node.val<val) node=node.right;else node=node.left;}return null;}
}
98.验证二叉搜索树
递归三步曲：
1、传入参数：根节点，最小值，最大值。从上往下遍历，一旦不满足则返回false，所以返回值为boolean类型。
2、终止条件：如果是节点为空，返回true；只有在前面都是true的情况下才会遍历到空节点，并传回true。
3、递归逻辑：如果中间节点小于最小值或大于最大值，则返回false；递归调用左子树和右子树，当两个结果都为true时返回。
代码如下：
class Solution {public boolean isValidBST(TreeNode root) {return validBST(Long.MIN_VALUE,Long.MAX_VALUE,root);}public boolean validBST(long lower, long upper,TreeNode root){if(root==null) return true;if(root.val<=lower || root.val>=upper) return false;return (validBST(lower,root.val,root.left))&&(validBST(root.val,upper,root.right));}
}
