Skip to content

Latest commit

 

History

History
192 lines (145 loc) · 6.79 KB

二叉树中递归带着回溯.md

File metadata and controls

192 lines (145 loc) · 6.79 KB

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

二叉树:以为使用了递归,其实还隐藏着回溯

补充一波

昨天的总结篇中还在玩耍的你,该总结啦!(本周小结之二叉树),有两处问题需要说明一波。

求相同的树

还在玩耍的你,该总结啦!(本周小结之二叉树)中求100.相同的树的代码中,我笔误贴出了 求对称树的代码了,细心的同学应该都发现了。

那么如下我再给出求100. 相同的树 的代码,如下:

class Solution {
public:
    bool compare(TreeNode* tree1, TreeNode* tree2) {
        if (tree1 == NULL && tree2 != NULLreturn false;
        else if (tree1 != NULL && tree2 == NULLreturn false;
        else if (tree1 == NULL && tree2 == NULLreturn true;
        else if (tree1->val != tree2->valreturn false; // 注意这里我没有使用else

        // 此时就是:左右节点都不为空,且数值相同的情况
        // 此时才做递归,做下一层的判断
        bool compareLeft = compare(tree1->left, tree2->left);       // 左子树:左、 右子树:左
        bool compareRight = compare(tree1->right, tree2->right);    // 左子树:右、 右子树:右
        bool isSame = compareLeft && compareRight;                  // 左子树:中、 右子树:中(逻辑处理)
        return isSame;

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

以上的代码相对于:二叉树:我对称么? 仅仅修改了变量的名字(为了符合判断相同树的语境)和 遍历的顺序。

大家应该会体会到:认清判断对称树本质之后, 对称树的代码 稍作修改 就可以直接用来AC 100.相同的树。

递归中隐藏着回溯

二叉树:找我的所有路径?中我强调了本题其实是用到了回溯的,并且给出了第一个版本的代码,把回溯的过程充分的提现了出来。

如下的代码充分的体现出回溯:(257. 二叉树的所有路径)

class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val);
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) {
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) {
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

如下为精简之后的递归代码:(257. 二叉树的所有路径)

class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里
        if (cur->right) traversal(cur->right, path + "->", result); // 右 回溯就隐藏在这里
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

上面的代码,大家貌似感受不到回溯了,其实回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完,path依然是没有加上"->" 的,这就是回溯了。

为了把这份精简代码的回溯过程展现出来,大家可以试一试把:

if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里

改成如下代码:

path += "->";
traversal(cur->left, path, result); // 左

即:


if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
}

此时就没有回溯了,这个代码就是通过不了的了。

如果想把回溯加上,就要 在上面代码的基础上,加上回溯,就可以AC了。

if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
    path.pop_back(); // 回溯
    path.pop_back();
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
    path.pop_back(); // 回溯
    path.pop_back();
}

大家应该可以感受出来,如果把 path + "->"作为函数参数就是可以的,因为并有没有改变path的数值,执行完递归函数之后,path依然是之前的数值(相当于回溯了)

如果有点遗忘了,建议把这篇二叉树:找我的所有路径?在仔细看一下,然后再看这里的总结,相信会豁然开朗。

这里我尽量把逻辑的每一个细节都抠出来展现了,希望对大家有所帮助!

其他语言版本

Java:

Python:

Go: