Skip to content

Latest commit

 

History

History
326 lines (250 loc) · 10.7 KB

0617.合并二叉树.md

File metadata and controls

326 lines (250 loc) · 10.7 KB

欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

617.合并二叉树

题目地址:https://leetcode-cn.com/problems/merge-two-binary-trees/

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

617.合并二叉树

注意: 合并必须从两个树的根节点开始。

思路

相信这道题目很多同学疑惑的点是如何同时遍历两个二叉树呢?

其实和遍历一个树逻辑是一样的,只不过传入两个树的节点,同时操作。

递归

二叉树使用递归,就要想使用前中后哪种遍历方式?

本题使用哪种遍历都是可以的!

我们下面以前序遍历为例。

动画如下:

617.合并二叉树

那么我们来按照递归三部曲来解决:

  1. 确定递归函数的参数和返回值:

首先那么要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点。

代码如下:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
  1. 确定终止条件:

因为是传入了两个树,那么就有两个树遍历的节点t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了啊(如果t2也为NULL也无所谓,合并之后就是NULL)。

反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。

代码如下:

if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
  1. 确定单层递归的逻辑:

单层递归的逻辑就比较好些了,这里我们用重复利用一下t1这个树,t1就是合并之后树的根节点(就是修改了原来树的结构)。

那么单层递归中,就要把两棵树的元素加到一起。

t1->val += t2->val;

接下来t1 的左子树是:合并 t1左子树 t2左子树之后的左子树。

t1 的右子树:是 合并 t1右子树 t2右子树之后的右子树。

最终t1就是合并之后的根节点。

代码如下:

t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;

此时前序遍历,完整代码就写出来了,如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             //
        t1->left = mergeTrees(t1->left, t2->left);      //
        t1->right = mergeTrees(t1->right, t2->right);   //
        return t1;
    }
};

那么中序遍历也是可以的,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      //
        t1->val += t2->val;                             //
        t1->right = mergeTrees(t1->right, t2->right);   //
        return t1;
    }
};

后序遍历依然可以,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      //
        t1->right = mergeTrees(t1->right, t2->right);   //
        t1->val += t2->val;                             //
        return t1;
    }
};

但是前序遍历是最好理解的,我建议大家用前序遍历来做就OK。

如上的方法修改了t1的结构,当然也可以不修改t1和t2的结构,重新定一个树。

不修改输入树的结构,前序遍历,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点,不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

迭代法

使用迭代法,如何同时处理两棵树呢?

思路我们在二叉树:我对称么?中的迭代法已经讲过一次了,求二叉树对称的时候就是把两个树的节点同时加入队列进行比较。

本题我们也使用队列,模拟的层序遍历,代码如下:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空,val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空,加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空,加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空,就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空,就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

拓展

当然也可以秀一波指针的操作,这是我写的野路子,大家就随便看看就行了,以防带跑遍了。

如下代码中,想要更改二叉树的值,应该传入指向指针的指针。

代码如下:(前序遍历)

class Solution {
public:
    void process(TreeNode** t1, TreeNode** t2) {
        if ((*t1) == NULL && (*t2) == NULL) return;
        if ((*t1) != NULL && (*t2) != NULL) {
            (*t1)->val += (*t2)->val;
        }
        if ((*t1) == NULL && (*t2) != NULL) {
            *t1 = *t2;
            return;
        }
        if ((*t1) != NULL && (*t2) == NULL) {
            return;
        }
        process(&((*t1)->left), &((*t2)->left));
        process(&((*t1)->right), &((*t2)->right));
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        process(&t1, &t2);
        return t1;
    }
};

总结

合并二叉树,也是二叉树操作的经典题目,如果没有接触过的话,其实并不简单,因为我们习惯了操作一个二叉树,一起操作两个二叉树,还会有点懵懵的。

这不是我们第一次操作两颗二叉树了,在二叉树:我对称么?中也一起操作了两棵二叉树。

迭代法中,一般一起操作两个树都是使用队列模拟类似层序遍历,同时处理两个树的节点,这种方式最好理解,如果用模拟递归的思路的话,要复杂一些。

最后拓展中,我给了一个操作指针的野路子,大家随便看看就行了,如果学习C++的话,可以在去研究研究。

其他语言版本

Java:

class Solution {
    // 递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        TreeNode newRoot = new TreeNode(root1.val + root2.val);
        newRoot.left = mergeTrees(root1.left,root2.left);
        newRoot.right = mergeTrees(root1.right,root2.right);
        return newRoot;
    }
}
class Solution {
   // 迭代
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root2);
        stack.push(root1);
        while (!stack.isEmpty()) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            node1.val += node2.val;
            if (node2.right != null && node1.right != null) {
                stack.push(node2.right);
                stack.push(node1.right);
            } else {
                if (node1.right == null) {
                    node1.right = node2.right;
                }
            }
            if (node2.left != null && node1.left != null) {
                stack.push(node2.left);
                stack.push(node1.left);
            } else {
                if (node1.left == null) {
                    node1.left = node2.left;
                }
            }
        }
        return root1;
    }
}

Python:

Go: