🎈LeetCode654.最大二叉树

链接：654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

还是用递归三部曲做，代码如下：

public TreeNode constructMaximumBinaryTree(int[] nums) {// 1 <= nums.length <= 1000return bulid(nums,0,nums.length-1);}public TreeNode bulid(int[] nums,int start,int end){// 0 <= nums[i] <= 1000if(start>end){return null;}if(start==end){return new TreeNode(nums[start]);}int max=0;int index=0;for(int i=start;i<=end;i++){if(nums[i]>max){max=nums[i];index=i;}}TreeNode root=new TreeNode(max);root.left=bulid(nums,start,index-1);root.right=bulid(nums,index+1,end);return root;}

🎈LeetCode617.合并二叉树

链接：617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {TreeNode root=new TreeNode();if(root1==null && root2==null){return null;}else if(root1==null && root2!=null){return root2;// return new TreeNode(root2.val);}else if(root1!=null && root2==null){return root1;// return new TreeNode(root1.val);}else{root.val=root1.val+root2.val;// return new TreeNode(root1.val+root2.val);root.left= mergeTrees(root1.left,root2.left);root.right=mergeTrees(root1.right,root2.right);}return root;}

🎈LeetCode700. 二叉搜索树中的搜索

链接：700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

public TreeNode searchBST(TreeNode root, int val) {//root 是二叉搜索树 if(root==null){return null;}TreeNode node=new TreeNode(0);if(root.val>val){node=searchBST(root.left,val);}else if(root.val<val){node=searchBST(root.right,val);}else{return root;}return node;}

🎈LeetCode98. 验证二叉搜索树

链接：98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

二叉搜索树的中序遍历正好是一个递增的序列，可以利用中序遍历来判断是不是二叉搜索树，代码如下：

public TreeNode searchBST(TreeNode root, int val) {//递归法//root 是二叉搜索树 if(root==null){return null;}TreeNode node=new TreeNode(0);if(root.val>val){node=searchBST(root.left,val);}else if(root.val<val){node=searchBST(root.right,val);}else{return root;}return node;}

public boolean isValidBST(TreeNode root) {// 迭代法if(root==null){return true;}Stack<TreeNode> st=new Stack<>();st.push(root);TreeNode pre=null;while(!st.isEmpty()){TreeNode node=st.peek();if(node!=null){st.pop();if(node.right!=null){st.push(node.right);}st.push(node);st.push(null);if(node.left!=null){st.push(node.left);}}else{st.pop();TreeNode temp=st.pop();if(pre!=null && pre.val>=temp.val){return false;}pre=temp;}}return true;}