目录
🎈LeetCode654.最大二叉树
🎈LeetCode617.合并二叉树
🎈LeetCode700. 二叉搜索树中的搜索
🎈LeetCode98. 验证二叉搜索树
🎈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;}