java算法第20天 | ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树

和根据后/前中序遍历数组生成树结构的思路一样。首先要明确参数和返回值。
每次递归需要传入数组，和开始和结束的位置，返回的是二叉树的根节点。

/*** 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) {return getTree(nums,0,nums.length);}public TreeNode getTree(int[] nums,int left,int right){if(right-left<1){return null;}// if(right-left==1) return new TreeNode(nums[left]);//判断当只剩一个节点时的情况，可写可不写，不写则进入下一层递归在判断int maxNum=Integer.MIN_VALUE;int maxIndex=-1;for(int i=left;i<right;i++){if(nums[i]>maxNum){maxIndex=i;maxNum=nums[i];} }TreeNode root=new TreeNode(maxNum);root.left=getTree(nums,left,maxIndex);root.right=getTree(nums,maxIndex+1,right);return root;}
}

同时遍历两个二叉树，可以不创建新的节点，直接在其中一个数的基础上操作。

/*** 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 mergeTrees(TreeNode root1, TreeNode root2) {return getTree(root1,root2);}public TreeNode getTree(TreeNode node1,TreeNode node2){if(node1==null) return node2;if(node2==null) return node1;node1.val+=node2.val;node1.left=getTree(node1.left,node2.left);node1.right=getTree(node1.right,node2.right);return node1;}
}

因为是二叉搜索树，不必左右子树都遍历。

/*** 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 searchBST(TreeNode root, int val) {return getTreeNode(root,val);}public TreeNode getTreeNode(TreeNode node,int val){if(node==null) return null;if(node.val==val) return node;if(val<node.val) return getTreeNode(node.left,val);else return getTreeNode(node.right,val);}
}

这道题最直观的解法是直接用中序遍历得到一个数组，判断数组是否是由小到大的。
但是我试了这种解法超时。

因此使用双指针优化的方法，假设当前遍历的节点是node，定义一个全局变量节点存储node中序遍历的上一个节点。

/*** 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 {TreeNode pre;public boolean isValidBST(TreeNode root) {return dfs(root);}public boolean dfs(TreeNode node){if(node==null) return true;boolean left=dfs(node.left);if(pre!=null && pre.val>=node.val) return false;pre=node;boolean right=dfs(node.right);return left && right;}
}