递归实现#

这题的思路其实不需要想的太复杂，遍历两棵树的逻辑其实和遍历一棵树是一样的，只不过需要传入两个树的根节点。

所以我们的递归函数需要输入的是两个树的根节点， 返回合并后的根节点。

然后要确定递归函数的终止条件：

1. 如果两个树都是空的，返回空节点
2. 如果树1是空的，那么合并的只有树2，也就是可以返回树2的根节点
3. 如果树2是空的，那么合并的只有树1，也就是可以返回树1的根节点

之后是确定单层的递归逻辑，当两个树都不为空时，我们就可以新建一个节点，值为两棵树的根节点之和。 然后递归调用左子树和右子树的合并函数，分别传入两棵树的左子树和右子树。

整体代码如下：

TreeNode* mergeTrees(TreeNode* ro root1, TreeNode* root2) {
    if (ro root1 == nullptr && root2 == nullptr) { // 如果两个树都是空的，返回空
        return nullptr;
    }
    if (ro root1 == nullptr) { // 如果树1是空的，返回树2
        return root2;
    }
    if (root2 == nullptr) { // 如果树2是空的，返回树1
        return root1;
    }
    // 如果两个树都不为空，那么就合并
    TreeNode* node = new TreeNode(ro root1->val + root2->val); // 新建一个节点，值为两棵树的根节点之和
    node->left = mergeTrees(ro root1->left, root2->left); // 左子树合并
    node->right = mergeTrees(ro root1->right, root2->right); // 右子树合并

    return node; // 返回合并后的节点
}

其实这里的遍历顺序用三种之一都可以，不过用前序遍历更好理解。

迭代实现#

对于同时操作两棵树，我们可以使用队列，将两棵树的节点同时加入队列进行比较，最后我们可以返回树1的根节点。

同样的，我们有以下条件：

1. 如果两棵树左节点都不为空，加入队列
2. 如果两棵树右节点都不为空，加入队列
3. root1的左节点 为空 root2左节点不为空，就赋值过去
4. root1的右节点 为空 root2右节点不为空，就赋值过去

最后我们只需要返回树1的根节点即可（因为修改的是root1）。

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if  root1 == NULL) return root2;
    if (root2 == NULL) return root1;
    queue<TreeNode*> que;
    que.push root1);
    que.push(root2);
    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);
        }

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

递归实现#

因为二叉搜索树的性质是左子树的值小于根节点的值，右子树的值大于根节点的值，所以我们可以根据这个性质来进行搜索。

• 如果当前节点的值等于目标值，返回当前节点
• 如果当前节点的值大于目标值，搜索左子树
• 如果当前节点的值小于目标值，搜索右子树

根据这个逻辑我们可以有以下递归的写法：

TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val) return root; // 1. 如果当前节点为空或者当前节点的值等于目标值，返回当前节点
    // 2. 如果当前节点的值大于目标值，搜索左子树
    if (root->val > val) return searchBST(root->left, val);
    // 3. 如果当前节点的值小于目标值，搜索右子树
    if (root->val < val) return searchBST(root->right, val);
    // 都没有找到，返回空节点
    return nullptr;
}

迭代实现#

迭代的写法相对就简单了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。并且对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

从根节点开始，如果当前节点的值等于目标值，返回当前节点；如果当前节点的值大于目标值，搜索左子树；如果当前节点的值小于目标值，搜索右子树。

TreeNode* searchBST(TreeNode* root, int val) {
    TreeNode* node = root; // 定义一个节点，指向根节点
    while (node != nullptr) { // 如果节点不为空
        if (node->val == val) { // 如果节点的值等于目标值，返回该节点
            return node;
        } else if (node->val < val) { // 如果节点的值小于目标值，去右子树查找
            node = node->right;
        } else { // 如果节点的值大于目标值，去左子树查找
            node = node->left;
        }
    }
    return nullptr; // 如果没有找到，返回空
}