二叉树刷题总结：二叉树的修改与构造
翻转二叉树
翻转一棵二叉树。
思路
把每个节点的左右孩子交换一下。
代码如下：
/**
* 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;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
时间复杂度：O(N)，其中 N 为二叉树节点的数目。
空间复杂度：O(N)。
构造二叉树
二叉树刷题总结：二叉树的遍历方式
最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树，并且输出这个树的根节点。
思路
构造树我们一般都采用前序遍历的方式去构造，因为前序遍历先构造中间节点，然后递归构造左子树和右子树。
于是，递归的思路如下：
- 递归的传参和返回值：传参为传入的存放元素的数组，返回值为指向二叉树根节点的指针；
- 终止条件为：当数组中只有一个元素的时候，代表当前元素是叶子节点，则我们就为此元素定义一个新节点，并返回；
- 确定单层递归逻辑，这里要处理的工作分为三步：首先找到数组中最大值和下标，构建根节点，然后依据下标构建左子树，最后构建右子树；
代码如下：
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode node = new TreeNode(0);
// 当遇到只有一个元素，则表示为叶子节点
if (nums.length == 1){
node.val = nums[0];
return node;
}
// 中间节点
int maxIndex = getMax(nums);
node.val = nums[maxIndex];
// 如果有左子树，生成左子树，
if (maxIndex > 0){
int[] leftNum = Arrays.copyOfRange(nums, 0, maxIndex);
node.left = constructMaximumBinaryTree(leftNum);
}
// 如果有右子树，生成右子树
if (maxIndex < nums.length - 1) {
int[] right = Arrays.copyOfRange(nums, maxIndex+1, nums.length);
node.right = constructMaximumBinaryTree(right);
}
return node;
}
public int getMax(int[] nums){
int maxIndex = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] > nums[maxIndex]) maxIndex = i;
}
return maxIndex;
}
}
以上的代码比较冗余，执行的效率很低，如下图所示：
image
于是，我们可以对其进行一次优化，在上面的思路中，我们每次都需要去开辟左子树和右子树所在的数组空间。我们可以在这一步上对其进行优化，通过数组下标索引直接在原数组上操作来替换每次分割定义新的数组。
代码如下：
/**
* 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;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length);
}
public TreeNode construct(int[] nums, int l, int r){
if (l == r) return null;
int max_i = max(nums, l, r);
TreeNode node = new TreeNode(nums[max_i]);
node.left = construct(nums, l, max_i);
node.right = construct(nums, max_i+1, r);
return node;
}
public int max(int[] nums, int l, int r){
int max_i = l;
for (int i = l; i < r; i++) {
if (nums[max_i] < nums[i]){
max_i = i;
}
}
return max_i;
}
}
这样执行效率就非常高了。
image
时间复杂度：O(n^2)。方法 construct 一共被调用 n 次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。最坏的情况下，数组 nums 有序，总的复杂度为 O(n^2)。
空间复杂度：O(n)。递归调用深度为 n。平均情况下，长度为 n 的数组递归调用深度为O(logn)。
合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
思路
利用前序遍历，同时遍历俩棵树。
- 确定递归的参数与返回值：传参为俩棵二叉树的根节点，返回值为合并后的二叉树的根节点；
- 递归终止条件：当二叉树 t1 为 null 时，返回 t2。反之，当 t2 为空时，返回 t1。
- 单层递归逻辑：当俩棵树的节点都不为空时，将俩节点值相加。然后，再合并俩棵树的左子树和右子树。
代码如下：
/**
* 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;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
TreeNode node = new TreeNode(root1.val + root2.val);
node.left = mergeTrees(root1.left, root2.left);
node.right = mergeTrees(root1.right, root2.right);
return node;
}
}
最后
好了，关于二叉树的修改与构造总结到这里就结束了，回顾一下，二叉树的翻转我们只需要把每个节点的左右孩子交换一下就可以完成翻转了。构造二叉树的解题思路为找到中间节点，然后再找出左子树的区间和右子树的区间，从而通过递归的方式去构造二叉树。合并二叉树我们可以利用前序遍历的方式同时遍历俩棵树从而完成合并。相信看完这篇文章，你会对二叉树遍历有一定的了解，感谢你的阅读。
本文分享自 HelloWorld杰少 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
