仅为个人记录复盘学习历程,解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
654.最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
提供参数:数组nums
主要操作:
递归三要素(使用索引不重复定义数组/列表)
1.返回值类型和参数:
返回构造出的树的根结点root,输入参数数组nums。
2.终止条件:
左指针left>=右指针时,返回空指针null。
3.单层递归逻辑:
3.1获取数组中的最大值及其索引。
3.2使用最大值构造节点。
3.3使用索引递归设置node的左右子结点。
代码大致如下:
public TreeNode constructMaximumBinaryTree(int[] nums) {
List<Integer>numsList=new ArrayList<>();
for(int i=0;i<nums.length;i++){
numsList.add(nums[i]);
}
return traversal(numsList,0,numsList.size());
}
public TreeNode traversal(List<Integer>nums,int left,int right){
//1.终止条件
if(left>=right)return null;
//2.单层递归逻辑
//2.1寻找最大值分界点
int deleteNum=nums.get(left);
int deleteIndex=left;
for(int i=left;i<right;i++){
if(deleteNum<nums.get(i)){
deleteNum=nums.get(i);
deleteIndex=i;
}
}
//构造节点
TreeNode node=new TreeNode(deleteNum);
node.left=traversal(nums,left,deleteIndex);
node.right=traversal(nums,deleteIndex+1,right);
return node;
}
617.合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
提供参数:根结点root1,根结点root2。
主要操作:
递归三要素
1.返回值类型和输入参数:
需要返回一个合并后的树的根结点,返回值类型为TreeNode,需要输入两个树来进行合并,输入参数为:TreeNode root1, TreeNode root2。
2.终止条件:
当1树的节点为空时返回2树的节点;
当2树的节点为空时返回1树的节点。
3.单层递归逻辑:
计算中间节点的值为1树在该结点的值+2树在该结点的值。
递归设置新树的左右子结点。
在本题中使用1树来作为新的树(在1树上做修改作为结果返回)。
代码大致如下:
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;
}
标签:结点,随想录,节点,二叉树,root2,left,root1,日记,刷题
From: https://blog.csdn.net/weixin_73939095/article/details/143478519