C++ 编程练习题: 如何合并两个二叉树?

阅读 桌面完整版

题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合.

C/C++ 中二叉树的定义

在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义.

 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

递归, 深度优先

基本上, 算法题中的树类问题都可以用递归来实现, 递归的精髓就是深度优先遍历树.

如果我们不改变输入的两颗二叉树, 我们可以新建一颗二叉树用于合并.

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* root;
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        root = new TreeNode(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 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        t1->val += t2-gt;val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

两种递归实现方法的算法复杂度都是 O(m) 其中 m 就是最小结点那个数的结点数. 两种方法的空间复杂度都是 O(m) 因为递归都需要用到堆栈, 并且树有可能是倾斜的, 也就是退化成单向链表. 但平均上, 空间复杂度是 O(logm) – 也就是结点数为 m 的层数.

自己用堆栈实现的DFS深度优先搜索算法
我们可以用堆栈来自己实现树的深度优先搜索算法.

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        stack< pair<TreeNode*, TreeNode*> > st;
        st.push(make_pair(t1, t2));
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur.first == nullptr || cur.second == nullptr) {
                continue;
            }
            cur.first->val += cur.second->val; // 累加值
            if (cur.first->left == nullptr) { // 第一颗树的左树为空, 那么就用第二颗树的左树
                cur.first->left = cur.second->left;
            } else {
                st.push(make_pair(cur.first->left, cur.second->left));
            }
            if (cur.first->right == nullptr) { // 第一颗树的右树为空, 那么就用第二颗树的右树
                cur.first->right = cur.second->right;
            } else {
                st.push(make_pair(cur.first->right, cur.second->right));
            }
        }       
        return t1;
    }
};

这个和用递归, 实现的空间复杂度和算法复杂度都是一样的: O(m)

英文: C++ Coding Exercise – How to Merge Two Binary Trees?

C/C++编程

• 理解C++中的std::transform_reduce及示例
• 使用原子 TAS 指令实现自旋锁
• C++中检测编译时与运行时: if consteval 与 std::is_constant_evaluated()
• C++ 转发引用: 完美转发的关键
• 理解 C++ 中的 dynamic_cast: 安全的向下转型与向上转型
• C与C++: restrict关键字及其在编译器优化中的作用
• C++的左值/lvalue, 右值/rvalue和右值引用/rvalue references
• C++中的assert和static_assert的区别
• C++: auto_ptr智能指针被弃用
• C++中的consteval是什么? 它与const和constexpr有何不同?
• C++ 教程: 用std::move来移动所有权
• C++中的 const和constexpr 比较
• 简易教程: C++的智能指针
• C++ 编程练习题: 如何合并两个二叉树?
• C++ 编程练习题 - 找出第三大的数
• C++ 编程练习题 - 最多连续的 1
• C++ 编程练习题 - 左子树叶节点之和 (深度优先+广度优先+递归)
• C++ 编程练习题 - 最多水容器 (递归)
• C++的异步编程: std::future, std::async 和 std::promise
• C编程练习题: 翻转整数位
• C++编程练习题: 找出字符串的所有大小小组合
• C/C++ 中的内存管理器(堆与栈)
• C++编程练习题: 对两单向链表求和

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版