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

617.合并二叉树

力扣题目链接

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

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

示例 1:

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

思路

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

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

递归

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

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

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

动画如下：

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

确定递归函数的参数和返回值：

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

代码如下：

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点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

确定单层递归的逻辑：

单层递归的逻辑就比较好些了，这里我们用重复利用一下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;

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

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;
    }
}

class Solution {
    // 使用队列迭代
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 ==null) return root1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            // 此时两个节点一定不为空，val相加
            node1.val = node1.val + node2.val;
            // 如果两棵树左节点都不为空，加入队列
            if (node1.left != null && node2.left != null) {
                queue.offer(node1.left);
                queue.offer(node2.left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1.right != null && node2.right != null) {
                queue.offer(node1.right);
                queue.offer(node2.right);
            }
            // 若node1的左节点为空，直接赋值
            if (node1.left == null && node2.left != null) {
                node1.left = node2.left;
            }
            // 若node2的左节点为空，直接赋值
            if (node1.right == null && node2.right != null) {
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

Python

递归法 - 前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # 递归终止条件: 
        #  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None. 
        if not root1: 
            return root2
        if not root2: 
            return root1
        # 上面的递归终止条件保证了代码执行到这里root1, root2都非空. 
        root1.val += root2.val # 中
        root1.left = self.mergeTrees(root1.left, root2.left) #左
        root1.right = self.mergeTrees(root1.right, root2.right) # 右
        
        return root1 # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间.

迭代法

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1: 
            return root2
        if not root2: 
            return root1

        queue = deque()
        queue.append(root1)
        queue.append(root2)

        while queue: 
            node1 = queue.popleft()
            node2 = queue.popleft()
            # 更新queue
            # 只有两个节点都有左节点时, 再往queue里面放.
            if node1.left and node2.left: 
                queue.append(node1.left)
                queue.append(node2.left)
            # 只有两个节点都有右节点时, 再往queue里面放.
            if node1.right and node2.right: 
                queue.append(node1.right)
                queue.append(node2.right)

            # 更新当前节点. 同时改变当前节点的左右孩子. 
            node1.val += node2.val
            if not node1.left and node2.left: 
                node1.left = node2.left
            if not node1.right and node2.right: 
                node1.right = node2.right

        return root1

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //前序遍历（递归遍历，跟105 106差不多的思路）
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
    var value int 
    var nullNode *TreeNode//空node，便于遍历
    nullNode=&TreeNode{
        Val:0,
        Left:nil,
        Right:nil}
    switch {
        case t1==nil&&t2==nil: return nil//终止条件
        default : //如果其中一个节点为空，则将该节点置为nullNode，方便下次遍历
        if t1==nil{
            value=t2.Val
            t1=nullNode
        }else if t2==nil{
            value=t1.Val
            t2=nullNode
        }else {
            value=t1.Val+t2.Val
        }
    }
    root:=&TreeNode{//构造新的二叉树
        Val: value,
        Left: mergeTrees(t1.Left,t2.Left),
        Right: mergeTrees(t1.Right,t2.Right)}
    return root
}

// 前序遍历简洁版
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

// 迭代版本
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    queue := make([]*TreeNode,0)
    if root1 == nil{
        return root2
    }
    if root2 == nil{
        return root1
    }
    queue = append(queue,root1)
    queue = append(queue,root2)

    for size:=len(queue);size>0;size=len(queue){
        node1 := queue[0]
        queue = queue[1:]
        node2 := queue[0]
        queue = queue[1:]
        node1.Val += node2.Val
        // 左子树都不为空
        if node1.Left != nil && node2.Left != nil{
            queue = append(queue,node1.Left)
            queue = append(queue,node2.Left)
        }
        // 右子树都不为空
        if node1.Right !=nil && node2.Right !=nil{
            queue = append(queue,node1.Right)
            queue = append(queue,node2.Right)
        }
        // 树 1 的左子树为 nil，直接接上树 2 的左子树
        if node1.Left == nil{
            node1.Left = node2.Left
        }
        // 树 1 的右子树为 nil，直接接上树 2 的右子树
        if node1.Right == nil{
            node1.Right = node2.Right
        }
    }
    return root1
}

JavaScript

递归法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
    const preOrder = (root1, root2) => {
        if (!root1)
            return root2
        if (!root2)
            return root1;
        root1.val += root2.val;
        root1.left = preOrder(root1.left, root2.left);
        root1.right = preOrder(root1.right, root2.right);
        return root1;
    }
    return preOrder(root1, root2);
};

迭代法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    if (root1 === null) return root2;
    if (root2 === null) return root1;

    let queue = [];
    queue.push(root1);
    queue.push(root2);
    while (queue.length) {
        let node1 = queue.shift();
        let node2 = queue.shift();;
        node1.val += node2.val;
        if (node1.left !== null && node2.left !== null) {
            queue.push(node1.left);
            queue.push(node2.left);
        }
        if (node1.right !== null && node2.right !== null) {
            queue.push(node1.right);
            queue.push(node2.right);
        }
        if (node1.left === null && node2.left !== null) {
            node1.left = node2.left;
        }
        if (node1.right === null && node2.right !== null) {
            node1.right = node2.right;
        } 
    }
    return root1;
};

TypeScript

递归法：

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if (root1 === null) return root2;
    if (root2 === null) return root1;
    const resNode: TreeNode = new TreeNode(root1.val + root2.val);
    resNode.left = mergeTrees(root1.left, root2.left);
    resNode.right = mergeTrees(root1.right, root2.right);
    return resNode;
};

迭代法：

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if (root1 === null) return root2;
    if (root2 === null) return root1;
    const helperQueue1: TreeNode[] = [],
        helperQueue2: TreeNode[] = [];
    helperQueue1.push(root1);
    helperQueue2.push(root2);
    let tempNode1: TreeNode,
        tempNode2: TreeNode;
    while (helperQueue1.length > 0) {
        tempNode1 = helperQueue1.shift()!;
        tempNode2 = helperQueue2.shift()!;
        tempNode1.val += tempNode2.val;
        if (tempNode1.left !== null && tempNode2.left !== null) {
            helperQueue1.push(tempNode1.left);
            helperQueue2.push(tempNode2.left);
        } else if (tempNode1.left === null) {
            tempNode1.left = tempNode2.left;
        }
        if (tempNode1.right !== null && tempNode2.right !== null) {
            helperQueue1.push(tempNode1.right);
            helperQueue2.push(tempNode2.right);
        } else if (tempNode1.right === null) {
            tempNode1.right = tempNode2.right;
        }
    }
    return root1;
};

Scala

递归:

object Solution {
  def mergeTrees(root1: TreeNode, root2: TreeNode): TreeNode = {
    if (root1 == null) return root2 // 如果root1为空，返回root2
    if (root2 == null) return root1 // 如果root2为空，返回root1
    // 新建一个节点，值为两个节点的和
    var node = new TreeNode(root1.value + root2.value)
    // 往下递归
    node.left = mergeTrees(root1.left, root2.left)
    node.right = mergeTrees(root1.right, root2.right)
    node // 返回node，return关键字可以省略
  }
}

迭代:

object Solution {
  import scala.collection.mutable
  def mergeTrees(root1: TreeNode, root2: TreeNode): TreeNode = {
    if (root1 == null) return root2
    if (root2 == null) return root1
    var stack = mutable.Stack[TreeNode]()
    // 先放node2再放node1
    stack.push(root2)
    stack.push(root1)
    while (!stack.isEmpty) {
      var node1 = stack.pop()
      var node2 = stack.pop()
      node1.value += node2.value
      if (node1.right != null && node2.right != null) {
        stack.push(node2.right)
        stack.push(node1.right)
      } else {
        if(node1.right == null){
          node1.right = node2.right
        }
      }
      if (node1.left != null && node2.left != null) {
        stack.push(node2.left)
        stack.push(node1.left)
      } else {
        if(node1.left == null){
          node1.left = node2.left
        }
      }
    }
    root1
  }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0617.合并二叉树.md

0617.合并二叉树.md

617.合并二叉树

思路

递归

迭代法

拓展

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Scala

Files

0617.合并二叉树.md

Latest commit

History

0617.合并二叉树.md

File metadata and controls

617.合并二叉树

思路

递归

迭代法

拓展

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Scala