刷代码随想录有感(53):合并二叉树

发布于:2024-05-03 ⋅ 阅读:(142) ⋅ 点赞:(0)

题干:

代码(递归实现):

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;

    }
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2){//重新定义一棵树
    if(root1 == NULL)return root2;
    if(root2 == NULL)reutrn root1;

    TreeNode* node = new TreeNode(0);
    node -> left = mergeTrees(root1-> left, root2->left);
    node -> right = mergeTrees(root1-> right, root2-> right);
    return node;

代码(迭代实现):在判断二叉树是否对称时涉及到了判断两个子树,用到了队列,那么处理两个树就使用队列。

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//这里也是将树2覆盖到树1上
        if(root1 == NULL)return root2;
        if(root2 == NULL)return root1;
        queue<TreeNode*>que;
        if(root1 != NULL)que.push(root1);
        if(root2 != NULL)que.push(root2);
        while(!que.empty()){
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();

            node1-> val += node2->val;

            if(node1->left && node2-> left){
                que.push(node1->left);
                que.push(node2->left);
            }
            if(node1-> right && node2->right){
                que.push(node1->right);
                que.push(node2->right);
            }
            if(!node1->left && node2->left){//都是判断树1左右是否空,空就让树2的左右覆盖,不会考虑树2
                node1->left = node2->left;
            }
            if(!node1->right && node2->right){
                node1->right = node2->right;
            }
        }
        return root1;

    }


网站公告

今日签到

点亮在社区的每一天
去签到