- 二叉树的构造默认如下：
/**
* 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;
* }
* }
*/
654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode node = construct(nums, 0, nums.length);//本题数组区间为左闭右开
return node;
}
TreeNode construct(int[] nums,int begin,int end){
if(nums.length==1){
return new TreeNode(nums[0]);//数组的长度为1，返回数组中的数构建的结点
}
//遍历数组，得到最大值的下标
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
for (int i = begin; i < end; i++) {
map.put(nums[i], i);//数组中的值为key，下标为value
max = Math.max(max,nums[i]);//找到数组中的最大值
}
int index = map.get(max);//数组中最大值的下标
TreeNode node = new TreeNode(max);//构建结点
if(index>begin){//如果左区间>=1
node.left = construct(nums,begin,index);
}
if(index<end-1){//如果右区间>=1
node.right = construct(nums,index+1,end);
}
return node;
}
}
- 还是构造二叉树的题目，但是比着昨天的两道要简单太多了，感觉自己也慢慢理解二叉树的递归构造
617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
ψ(｀∇´)ψ 我的思路
- 前序遍历两棵树的所有结点（思路题目上写的很清楚了）
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
TreeNode node;
if (root1 == null && root2 == null) {
return null;
} else if (root1 == null && root2 != null) {
node = root2;
} else if (root2 == null && root1 != null) {
node = root1;
} else {
node = new TreeNode(root1.val+ root2.val);
node.left = mergeTrees(root1.left,root2.left);
node.right = mergeTrees(root1.right,root2.right);
}
return node;
}
}