代码随想录算法训练营day17(day19补) | 110.平衡二叉树 257.二叉树的所有路径 404.左叶子之和

刷题笔记day17

110.平衡二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

没有思路。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    int getheight(TreeNode* node) {
        if (!node) return 0; 
        int leftheight = getheight(node->left);
        if (leftheight == -1) return -1;
        int rightheight = getheight(node->right);
        if (rightheight == -1) return -1;
        int result;
        if (abs(leftheight - rightheight) > 1) return -1;
        result = 1 + max(leftheight, rightheight);
        return result;
    }
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return getheight(root) == -1 ? false : true;
    }
};

看了题解后的收获

对于回溯算法已经是非常复杂的递归了，如果再用迭代的话，就是自己给自己找麻烦，效率也并不一定高。虽然理论上所有的递归都可以用迭代法来实现，但有些场景的难度比较大。
（不纠结此题的迭代法）

257.二叉树的所有路径

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

没有思路。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    string pathtostr(vector<int>& path) {
        string str;
        for (int i = 0; i < path.size(); ++i) {
            str += to_string(path[i]);
            if (i != path.size()-1) {
                str += "->";
            }
        }
        return str;
    }
    void traversal(TreeNode *cur, vector<int> path, vector<string>& result) {
        path.push_back(cur->val);
        if (!cur->left && !cur->right) {
            string singlepath = pathtostr(path);
            result.push_back(singlepath);
            return;
        }
        if (cur->left) traversal(cur->left, path, result);
        if (cur->right) traversal(cur->right, path, result);
        return;
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (!root) return result;
        traversal(root, path, result);
        return result;
    }
};

看了题解后的收获

二叉树的所有路径应采用前序遍历的方式。

404.左叶子之和

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

如何判断当遍历到叶子节点的时候，是左节点还是右节点，我用了一个标志位，0为左，1为右，根节点输入为1，确保只有一个根节点的情况下节点值不加入sum中。

自己写的代码

class Solution {
public:
    void getleftleaf(TreeNode* node, int& sum, int lorr) {
        if (!node->left && !node->right && lorr == 0) 
        {
            sum +=node->val;
        }
        if (node->left) 
        {
            getleftleaf(node->left, sum, 0);
        }
        if (node->right) {
            getleftleaf(node->right, sum, 1);
        }
        return;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if (!root) return 0;
        getleftleaf(root, sum, 1);
        return sum;
    }
};

看了题解后修改的版本：

class Solution {
public:
    void getleftleaf(TreeNode* node, int& sum) {
        if (node->left && !node->left->left && !node->left->right) 
        {
            sum +=node->left->val;
        }
        if (node->left) {
            getleftleaf(node->left, sum);
        }
        if (node->right) {
            getleftleaf(node->right, sum);
        }
        return;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if (!root) return 0;
        getleftleaf(root, sum);
        return sum;
    }
};

看了题解后的收获

无法判断当前节点是否是左右节点，除了标志法也可以直接用父节点去进行判断。