代码随想录算法训练营第十七天 | 110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和

110.平衡二叉树

题目链接：110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

用递归的方式进行判断：记录当前节点左右子树的高度h1，h2，如果h1和h2的高度差绝对值不超过1，则说明当前节点及其子树可构成一个平衡二叉树。记当前节点的高度为max(h1, h2) + 1，再进行递归判断。

C++实现

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;

        int height;
        return dfs(root, height);
    }

    bool dfs(TreeNode* node, int& height){
        if(node == nullptr){
            height = 0;
            return true;
        }

        int height1, height2;
        bool lSuccess = dfs(node->left, height1);
        bool rSuccess = dfs(node->right, height2);

        height = max(height1, height2) + 1;

        return lSuccess && rSuccess && (abs(height1 - height2) <= 1);
    }
};

257.二叉树的所有路径

题目链接：257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

文章讲解/视频讲解：https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html

思路

用递归的方式进行遍历，可以采用前序遍历。记录下从根节点到叶节点沿途的路径，返回结果。具体见代码。

这里采用前序遍历来解决，那么也可以用迭代的前序遍历来做。

C++实现

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root == nullptr) return {};
        string path;
        vector<string> results;

        dfs(root, path, results);
        return results;
    }

    void dfs(TreeNode* node, string path, vector<string>& results){
        if(node->left == nullptr && node->right == nullptr){
            path += "->";
            path += to_string(node->val);
            results.push_back(path.substr(2, path.size() - 2));
            return;
        }

        path += "->";
        path += to_string(node->val);
        if(node->left != nullptr) dfs(node->left, path, results);
        if(node->right != nullptr) dfs(node->right, path, results);
    }
};

404.左叶子之和

题目链接：404.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

文章讲解/视频讲解：https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html

思路

用递归的思路来解决。每一次递归的处理中，对于当前节点，标记其来自于左节点或者右节点，如果当前节点属于叶子节点，且标记为左节点，则累加结果。

C++实现

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        int sum = 0;
        dfs(root, 2, sum);
        return sum;
    }

    void dfs(TreeNode* node, int dir, int& sum){
        // 定义dir = 0为左节点，dir = 1为右节点, dir = 2表示根节点
        if(dir == 0 && node->left == nullptr && node->right == nullptr){
            sum += node->val;
            return;
        }

        if(node->left) dfs(node->left, 0, sum);
        if(node->right) dfs(node->right, 1, sum);
    }
};