这是悦乐书的第 274 次更新, 第 290 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 142 题 (顺位题号是 617). 提供两个二叉树, 将其合并为新的二叉树, 也可以在其中一个二叉树上进行覆盖. 合并规则是如果两个节点重叠 (都不为空), 则将节点值加起来作为合并节点的新值. 否则, 其中一个不为空的节点将用作新树的节点. 例如:
- Tree 1 Tree 2
- 1 2
- / \ / \
- 3 2 1 3
- / \ \
- 5 4 7
合并后的新二叉树:
- 3
- / \
- 4 5
- / \ \
- 5 4 7
注意: 合并过程必须从两个树的根节点开始.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
合并两个二叉树, 首先我们需要遍历这两个二叉树的所有节点, 其次是选择遍历顺序, 是前序, 中序还是后序, 而题目说了要从根节点开始, 那么我们选择前序遍历. 二叉树的常规操作有递归, 迭代的方法, 此处我们选择递归的方法.
直接使用递归, 使用前序遍历的方式, 遍历 t1 和 t2, 顺序为根节点 --> 左子树 --> 右子树, 将每次处理的节点作为新树的节点. 此解法我是将递归方法独立出来了, 你也可以直接在原方法里写.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
- return helper(t1,t2);
- }
- public TreeNode helper(TreeNode t1, TreeNode t2){
- // 如果 t1 和 t2 的当前节点都为空, 直接返回 null
- if (t1 == null && t2 == null) {
- return null;
- }
- // 每次进递归方法里时, 都创建一个新节点, 当然, 你也可以用给的 t1 或者 t2 都行
- TreeNode t3 = new TreeNode(0);
- // 新节点的节点值
- t3.val = (t1 == null ? 0 : t1.val)+(t2 == null ? 0 : t2.val);
- // 新节点的左子树
- t3.left = helper(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
- // 新节点的右子树
- t3.right = helper(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
- return t3;
- }
- }
03 第二种解法
使用迭代的方法, 借助栈来实现, 与正常的单个二叉树借助栈来迭代的方法类似, 只是在两个二叉树的情况下, 多做了一些判断.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
- // 如果 t1 和 t2 都为空, 直接返回 null
- if (t1 == null && t2 == null) {
- return null;
- }
- // 如果 t2 为空, 直接返回 t1
- if (t2 == null) {
- return t1;
- }
- // 如果 t1 为空, 直接返回 t2
- if (t1 == null) {
- return t2;
- }
- // 使用两个栈
- Stack<TreeNode> stack = new Stack<TreeNode>();
- Stack<TreeNode> stack2 = new Stack<TreeNode>();
- stack.push(t1);
- stack2.push(t2);
- while (!stack.isEmpty() || !stack2.isEmpty()) {
- TreeNode temp = stack.pop();
- TreeNode temp2 = stack2.pop();
- if (temp == null || temp2 == null) {
- continue;
- }
- // 将新的节点值覆盖到 t1 上去
- temp.val = temp.val + temp2.val;
- // 如果 t1 的左子节点为 null, 那么新的 t1 的左子节点直接指向 t2 的左子节点, 否则同时入栈
- if (temp.left == null) {
- temp.left = temp2.left;
- } else {
- stack.push(temp.left);
- stack2.push(temp2.left);
- }
- // 与上面处理左子节点情况类似
- if (temp.right == null) {
- temp.right = temp2.right;
- } else {
- stack.push(temp.right);
- stack2.push(temp2.right);
- }
- }
- return t1;
- }
- }
04 第三种解法
同样是使用迭代的方法, 但是我们只使用一个栈, 栈中的泛型是二叉树数组.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
- // 如果 t1 和 t2 都为空, 直接返回 null
- if (t1 == null && t2 == null) {
- return null;
- }
- // 如果 t2 为空, 直接返回 t1
- if (t2 == null) {
- return t1;
- }
- // 如果 t1 为空, 直接返回 t2
- if (t1 == null) {
- return t2;
- }
- // 使用一个个栈
- Stack<TreeNode[]> stack = new Stack<>();
- stack.push(new TreeNode[]{t1, t2});
- // 其中的判断规则与上面两个栈的方法类似
- while (!stack.isEmpty()) {
- TreeNode[] t = stack.pop();
- if (t[0] == null || t[1] == null) {
- continue;
- }
- t[0].val += t[1].val;
- if (t[0].left == null) {
- t[0].left = t[1].left;
- } else {
- stack.push(new TreeNode[] {t[0].left, t[1].left});
- }
- if (t[0].right == null) {
- t[0].right = t[1].right;
- } else {
- stack.push(new TreeNode[] {t[0].right, t[1].right});
- }
- }
- return t1;
- }
- }
05 小结
此题本质上是考察二叉树的前序遍历, 及其递归, 迭代两种方法的实现, 如有不熟悉的, 可以去查漏补缺.
算法专题目前已日更超过四个月, 算法题文章 142 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/c911c5b13c8f