语言：Java/C++
654.最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。
随后找当前整个数组的最大值，根据最大值的下标将数组分为左子树和右子树，继续递归进行构建。
class Solution {
TreeNode traversal(int[] nums, int left, int right){
if(right <= left ) return null; //判空
if(right-left==1){ //判断是否为一个节点，左闭右开
return new TreeNode(nums[left]);
}
int maxIdx=left;
int maxValue=nums[left];
for(int i=left+1;i<right;i++){
if(nums[i]>maxValue){
maxValue=nums[i];
maxIdx=i;
}
}
TreeNode node = new TreeNode(maxValue);
node.left=traversal(nums, left, maxIdx);
node.right=traversal(nums, maxIdx+1, right);
return node;
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
return traversal(nums, 0, nums.length);
}
}617.合并二叉树 617.合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
这道题我的第一个想法是建立一个哈希表，层次遍历并存储第一个树的位置和值，如果该位置没有节点则为-1，随后创建新的节点，遍历第二个树，若当前位置已经有节点，则将两个节点值相加返回；如果第二棵树没有节点，但第一棵树有，则直接返回第一棵树的值；如果第一棵树没有节点，则直接返回第二棵树的值；若第二棵树的节点数少于第一棵树，则在遍历完第二棵树后直接将第一棵树的剩余节点返回。但是这个思路无疑增加了很多复杂性，其实遍历两棵树和遍历一棵树的思路是一样的，采用前序遍历即可。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null && root2!=null) return root2;
if(root2==null && root1!=null) return root1;
if (root1 == null && root2 == null) return null;
TreeNode root=new TreeNode(root1.val+root2.val);
root.left=mergeTrees(root1.left,root2.left);
root.right=mergeTrees(root1.right, root2.right);
return root;
}
}700.二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
因为本文的题设是二叉搜索树，所以这题就相对好办了，二叉搜索树是有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
因此，找到值等于val的点然后递归返回从这个点以后的树即可：
class Solution {
TreeNode traversal(TreeNode root, int val){
if(root==null||root.val==val) return root;
if(root.val>val){
return traversal(root.left, val);
}
else{
return traversal(root.right, val);
}
}
public TreeNode searchBST(TreeNode root, int val) {
return traversal(root, val);
}
}98.验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
考研时数据结构里有一个结论：中序遍历下，输出的二叉搜索树节点的数值是有序序列，因此可以先将树转换为列表或数组，再判断是否有序即可。注意在Java中，如果将树转换为列表List，则需要用.get和size()来获取列表的值和长度，如果是数组，因为不知道树的节点个数，所以需要先设置一个很大的值，所以也可以先将树转换为列表，再将列表转换为数组。
class Solution {
public void traversal(TreeNode root, List<Integer> vec){
if(root==null) return;
traversal(root.left, vec);
vec.add(root.val);
traversal(root.right, vec);
}
public boolean isValidBST(TreeNode root) {
List<Integer> res=new ArrayList<Integer>();
traversal(root, res);
// 将列表转换为数组
Integer[] arr=res.toArray(new Integer[res.size()]);
for(int i=1; i<arr.length;i++){
if(arr[i]<=arr[i-1]) {
return false;
}
}
return true;
}
}
