本文思路和更详细的解析来自于:代码随想录 (programmercarl.com)
LeetCode T654 最大二叉树
题目链接:654. 最大二叉树 - 力扣（LeetCode）
题目思路:
这题和昨天的题目很像,我们仍然需要构造一棵二叉树,我们仍然使用递归来完成,以下我们开始进行递归三部曲,我们需要知道,构建一棵树最好使用前序遍历
1.递归函数的设计,参数和返回值
这里返回值是TreeNode(树的一个节点),传入参数的我们需要操作的数组nums,和左右区间,注意,我们每一题要规定好左右区间的使用,不要一会儿使用闭区间,一会儿使用左闭右开区间.
public TreeNode constructMaximumBinaryTree1(int[] nums, int left, int right)
2.终止条件:
这里我们如果遇到空数组,我们需要返回,如果遇到单个节点,我们也可以直接返回
if(right-left<1) { return null; } if(right- left == 1) { return new TreeNode(nums[left]); }
3.单次递归的实现
int index = left;//最大值的下标 int maxVal= nums[index];//最大值 for(int i = left+1;i<right;i++) { if(nums[i]>maxVal) { maxVal = nums[i]; index = i; } } TreeNode node = new TreeNode(maxVal); node.left = constructMaximumBinaryTree1(nums,left,index);//左 node.right = constructMaximumBinaryTree1(nums,index+1,right);//右 return node;
这里注意,我们这样使用左右区间来定位是为了节省空间和创建新数组的书写方法,我们也可以使用每次创建左右数组的方式来区分左右区间.
题目代码:
class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return constructMaximumBinaryTree1(nums,0,nums.length); } public TreeNode constructMaximumBinaryTree1(int[] nums,int left,int right) { TreeNode node; //没有元素 if(right - left < 1) { return null; } //一个元素 if(right - left == 1) { return new TreeNode(nums[left]); } else { int index = left; int maxVal = nums[index]; for(int i = left+1;i<right;i++) { if(nums[i]>maxVal) { maxVal = nums[i]; index = i; } } node = new TreeNode(nums[index]); node.left = constructMaximumBinaryTree1(nums,left,index); node.right = constructMaximumBinaryTree1(nums,index+1,right); } return node; } }
LeetCode T617 合并二叉树
题目链接:617. 合并二叉树 - 力扣（LeetCode）
题目思路:
同时操作两棵二叉树,这里我们仍然使用递归去操作,使用前序遍历,这样比较符合直觉,当然中序和后序遍历也是可以的,这里我们使用前序来操作,我们仍然遵循递归三部曲
1.确定函数返回值和参数
我们这里希望每次返回的是TreeNode类型的数值,所以返回值是TreeNode,操作参数为两棵树
public TreeNode mergeTrees(TreeNode root1, TreeNode root2)
2.终止条件
这里我们是两棵树,首先如果第一棵树为空,我们直接返回第二棵树即可,第二棵树同理也是这样操作,有人可能觉得两棵树都为空的条件没有讨论,这里我们可以认为两棵树都为空的情况已经包含在内了,因为假设两棵树都为空,我返回任何一棵树实际上就都表示的是空节点了
if(root1 == null) { return root2; } if(root2 == null) { return root1; }
3.一次递归
这里我们再root1的基础上修改,就不用创建新的树进行操作了,节省空间和时间
root1.val +=root2.val; root1.left = mergeTrees(root1.left,root2.left); root1.right = mergeTrees(root1.right,root2.right); return root1;
题目代码:
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if(root1 == null) { return root2; } if(root2 == null) { return root1; } root1.val +=root2.val; root1.left = mergeTrees(root1.left,root2.left); root1.right = mergeTrees(root1.right,root2.right); return root1; } }
LeetCode T700 二叉搜索树中的搜索
题目链接:700. 二叉搜索树中的搜索 - 力扣（LeetCode）
题目思路:
这题我们只要根据二叉搜索树的左子树的值比根节点小,右子树的值比根节点大这个特性来解决问题就行,分递归法和迭代法解决问题
1.递归
1.1 函数参数和返回值
使用题目的原本的参数和返回值即可
1.2终止条件
只要树的节点为空或者只有一个节点而且恰好就等于我们要寻找的数值,直接发返回
if(root == null || root.val == val) { return root; }
1.3 递归过程
如果目前遍历的节点比我要寻找的数要大,就在右子树找,否则在左子树寻找
if(val<root.val) { return searchBST(root.left,val); } if(val>root.val) { return searchBST(root.right,val); } return null;
2.迭代法
思路和上面类似,不做赘述
class Solution { // 迭代，利用二叉搜索树特点，优化，可以不需要栈 public TreeNode searchBST(TreeNode root, int val) { while (root != null) if (val < root.val) root = root.left; else if (val > root.val) root = root.right; else return root; return null; } }
