算法随想Day15【二叉树】| LC110-平衡二叉树、LC257-二叉树的所有路径、LC404-左叶子之和

标签：LC110 return LC404 nullptr int 二叉树 str root left

LC110. 平衡二叉树

递归做法一次通过，其实也就是对比：某个节点的左子树和右子树的最大深度的绝对值不大于1，即可认为是平衡二叉树

class Solution {
public:
    bool flag;
    int checkBalanced(TreeNode* root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int leftheight = checkBalanced(root->left);
        int rightheight = checkBalanced(root->right);
        if (abs(leftheight - rightheight) > 1)
        {
            flag =  false;
        }
        int midheight = max(leftheight, rightheight) + 1;
        return midheight;
    }
    bool isBalanced(TreeNode* root)
    {
        flag = true;
        checkBalanced(root);
        return flag;
    }
};

LC257. 二叉树的所有路径

递归做法一次通过，递归回溯时，再拼接当前节点在前面

vector<string> binaryTreePaths(TreeNode* root)
{
    vector<string> str;
    if (root == nullptr)
    {
        return str;
    }
    vector<string> str1 = binaryTreePaths(root->left);
    vector<string> str2 = binaryTreePaths(root->right);
    if (str1.empty() != true)
    {
        for (auto it : str1)
        {
            str.push_back(to_string(root->val) + "->" + it);
        }
    }
    if (str2.empty() != true)
    {
        for (auto it : str2)
        {
            str.push_back(to_string(root->val) + "->" + it);
        }
    }
    if (str1.empty() == true && str2.empty() == true)
    {
        str.push_back(to_string(root->val));
    }
    return str;
}

但内存消耗很大，即使抽离vector str为引用也是如此

void checkPaths(TreeNode* root, vector<string>& str)
    {
        if (root == nullptr)
        {
            return;
        }
        vector<string> str1 = binaryTreePaths(root->left);
        vector<string> str2 = binaryTreePaths(root->right);
        if (str1.empty() != true)
        {
            for (auto it : str1)
            {
                str.push_back(to_string(root->val) + "->" + it);
            }
        }
        if (str2.empty() != true)
        {
            for (auto it : str2)
            {
                str.push_back(to_string(root->val) + "->" + it);
            }
        }
        if (str1.empty() == true && str2.empty() == true)
        {
            str.push_back(to_string(root->val));
        }
    }
    vector<string> binaryTreePaths(TreeNode* root)
    {
        vector<string> str;
        checkPaths(root, str);
        return str;
    }

LC404. 左叶子之和

第一次的写法，是误解了左叶子的概念a，原来指的是叶子节点，而且是属于左孩子的叶子节点。如[1, 2, 3, 4, 5]的结果是4，而不是2 + 4 = 6

int sumOfLeftLeaves(TreeNode* root)
{
    int sum = 0;
    int leftsum = 0, rightsum = 0;
    if (root == nullptr)
    {
        return sum;
    }
    if (root->left != nullptr)
    {
        leftsum += sumOfLeftLeaves(root->left);
    }
    if (root->right != nullptr)
    {
        rightsum += sumOfLeftLeaves(root->right);
    }
    sum = leftsum + rightsum + (root->left == nullptr ? 0 : root->left->val);
    return sum;
}

修改下，标记为is_left，且为叶子节点(root->left == nullptr && root->right == nullptr)才计数

int checkLeftLeaves(TreeNode* root, int is_left)
{
    int sum = 0;
    int leftsum = 0, rightsum = 0;
    if (root == nullptr)
    {
        return sum;
    }
    if (root->left != nullptr)
    {
        leftsum += checkLeftLeaves(root->left, 1);
    }
    if (root->right != nullptr)
    {
        rightsum += checkLeftLeaves(root->right, 0);
    }
    sum = leftsum + rightsum + (root->left == nullptr && root->right == nullptr && is_left == 1 ? root->val : 0);
    return sum;
}
int sumOfLeftLeaves(TreeNode* root)
{
    int sum = 0;
    sum = checkLeftLeaves(root, 0);
    return sum;
}

标签：LC110,return,LC404,nullptr,int,二叉树,str,root,left
From： https://www.cnblogs.com/Mingzijiang/p/17131784.html