Junyuan's Homepage

110. 平衡二叉树

题目链接：click here
文章讲解：click here
题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。
思路：
其实就是遍历求每个节点的高度，顺带判断它的左右子树的高度相差是否超过1

但是高度不重要，重要的是是否平衡，只有一个地方不平衡，就可以开始归的过程

后序递归法：

class Solution
{
public:
    int getheight(TreeNode *cur, bool &balance)
    {
        if (!cur)
            return 0;

        int height1 = getheight(cur->left, balance);
        if (!balance)
            return 0;
        int height2 = getheight(cur->right, balance);
        if (!balance)
            return 0;
        if (abs(height1 - height2) > 1)
        {
            balance = false;
            return 0;
        }

        return max(height1, height2) + 1;
    }

    bool isBalanced(TreeNode *root)
    {
        bool res = true;
        int _ = getheight(root, res);
        return res;
    }
};

257. 二叉树的所有路径

题目链接：click here
文章讲解：click here
题目描述：给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。使用迭代法完成二叉树的前中后序遍历
思路：
我的想法：递归获取左右子树的路径，然后再加上当前节点，汇总路径，返回上一层

递归代码：

class Solution
{
public:
    vector<string> binaryTreePaths(TreeNode *root)
    {
        if (!root)
            return vector<string>();

        string cur = std::to_string(root->val);
        vector<string> left = binaryTreePaths(root->left);      // 获取左子树路径
        vector<string> right = binaryTreePaths(root->right);    // 获取右子树路径

        vector<string> res;

        // 汇总路径
        for (auto path : left)
        {
            string temp_string = cur;
            temp_string = temp_string + "->" + path;
            res.push_back(temp_string);
        }

        for (auto path : right)
        {
            string temp_string = cur;
            temp_string = temp_string + "->" + path;
            res.push_back(temp_string);
        }
        // 左右子树路径都为空，则该节点为叶子节点，路径中不带 -> 符号
        if (left.size() == 0 && right.size() == 0)
        {
            res.push_back(cur);
        }

        return res;
    }
};

讲解思路：
递归+回溯，先向下找最深的路，然后返回一级，尝试另一条路，相当于每个节点有左右两条可以走，走到底了要返回来走另一条路。

结果是沿路收集的，直到走到底。

我的方法是从底向上收集。

回溯写法，需要注意，递进去，归的时候要还原路径。

递归函数传参：当前节点、当前已收集路径、汇总结果

递归终止条件：走到底了，将已收集的路径汇总到结果里

递归内部逻辑：用当前值，更新路径，然后尝试往左边收集，收集完回退，
再用当前值，更新路径，然后尝试往右边收集，收集完回退

class Solution
{
public:
    void traversal(TreeNode *cur, vector<int> &path, vector<string> &result)
    {
        // 走到底了，回收
        if (!(cur->left) && !(cur->right))
        {
            string res;
            for (int num : path)
            {
                res += (std::to_string(num) + "->");
            }
            res += std::to_string(cur->val);
            result.push_back(res);
            return;
        }

        // 尝试往左走
        if (cur->left)
        {
            path.push_back(cur->val);
            traversal(cur->left, path, result);
            path.pop_back(); // 回到岔路口
        }

        // 尝试往右走
        if (cur->right)
        {
            path.push_back(cur->val);
            traversal(cur->right, path, result);
            path.pop_back(); // 回到岔路口
        }
    }

    vector<string> binaryTreePaths(TreeNode *root)
    {
        vector<string> res;
        vector<int> path;
        if (!root)
            return vector<string>();
        traversal(root, path, res);
        return res;
    }
};

404. 左叶子之和

题目链接：click here
文章讲解：click here
题目描述：给定二叉树的根节点 root ，返回所有左叶子之和。
思路：
我的想法：前序遍历，给递归函数加一个标志位参数，表示当前这个节点是不是其父节点的左孩子节点。

如果左孩子节点是叶子，即为左叶子，则将数值累加。

迭代代码：

class Solution
{
public:
    void traversal(TreeNode *cur, int &sum, bool left)
    {
        if (!(cur->left) && !(cur->right))
        {
            if (left)
            {
                sum += cur->val;
            }
        }

        if (cur->left)
        {
            traversal(cur->left, sum, true);
        }

        if (cur->right)
        {
            traversal(cur->right, sum, false);
        }
    }
    int sumOfLeftLeaves(TreeNode *root)
    {
        if (!root)
            return 0;
        int sum = 0;
        traversal(root, sum, false);
        return sum;
    }
};

讲解思路：
抽象的定义递归函数的意义，就是求左子树的左叶子之和，再求右子树的左叶子之和，加起来就是整棵树的左叶子之和。
这其实就回答了“递归内部的逻辑”
不过还漏了一点，就是如果左子树就是一个左叶子，那么其值不必递归计算。真正赋值的地方也就是这里，而非下述递归终止的地方，因为那个地方只能知道自己是空或自己是叶子，往下无需再找，故而返回0。
而它无法知道自己是不是父节点的左孩子。
所以这个判断逻辑一定是在父节点中去做，也就是在“递归内部的逻辑”里实现

递归的传参及返回值：传入当前节点，返回当前节点的左叶子总和

递归终止：当前节点为空，返回0，当前节点没有左右子节点了，返回0

讲解代码：后序递归遍历

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right== NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左，是一棵树
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右，是一棵树

        int sum = leftValue + rightValue;               // 中，汇总左右的结果
        return sum;
    }
};

222. 完全二叉树的节点个数

题目链接：click here
文章讲解：click here
题目描述：给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
思路：
简单的做法就是遍历，然后累加个数

简单方法代码：适用于非完全二叉树

// 迭代，层序
class Solution
{
public:
    int countNodes(TreeNode *root)
    {
        int sum = 0;
        queue<TreeNode *> qt;
        if (root)
            qt.push(root);

        while (!qt.empty())
        {
            auto top = qt.front();
            qt.pop();

            sum++;
            if (top->left)
                qt.push(top->left);
            if (top->right)
                qt.push(top->right);
        }
        return sum;
    }
};

// 递归：后序
class Solution
{
public:
    int traserval(TreeNode *cur)
    {
        if (!cur)
            return 0;

        int left_num = traserval(cur->left);
        int right_num = traserval(cur->right);

        return left_num + right_num + 1;
    }

    int countNodes(TreeNode *root)
    {
        return traserval(root);
    }
};

讲解思路：
1. 利用好完全二叉树的性质：完全二叉树总能划分为几颗满二叉树
2. 满二叉树也是完全二叉树，同时它更加特殊，满二叉树向左遍历和向右遍历的深度一致
于是可以加快上述递归，即，无需递归到叶子节点，只需要抵达某颗满二叉树的根节点，即可无需向下递归了，因为判断它是根节点的时候已经获取了它的深度，那么直接根据公式节点数 = 2^depth - 1 即可提前结束递归。

也就是说递归的终止条件从原来的：当前节点为空，返回0
变为：当前节点为空，返回0 + 判断当前节点往下是否是满二叉树，若是，则返回 2^depth - 1

最终代码：

class Solution
{
public:
    int traserval(TreeNode *cur)
    {

        if (!cur)
            return 0;
        TreeNode *left = cur->left;
        TreeNode *right = cur->right;
        int deep_left = 1;
        int deep_right = 1;

        while (left)
        {
            deep_left++;
            left = left->left;
        }
        while (right)
        {
            deep_right++;
            right = right->right;
        }
        if (deep_left == deep_right)
        {
            return (1 << deep_left) - 1;
        }

        int left_num = traserval(cur->left);
        int right_num = traserval(cur->right);

        return left_num + right_num + 1;
    }

    int countNodes(TreeNode *root)
    {
        return traserval(root);
    }
};

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：

今日核心思想：
1. 二叉树的遍历以完成各种任务，比如判断树是否平衡、统计左叶子之和、计算完全二叉树的节点个数
2. 回溯初步：注意回溯和递归，递进去前修改了什么，归回来后就要返还什么。
平衡二叉树：
遍历统计高度，并附带判断左右子树高度是否偏差大于1

二叉树的所有路径：
回溯法：不断累计结果，直到叶子处统计一轮结果，再回溯到上游分岔口，向另一个方向探索。

左叶子之和：
递归：计算左子树的左叶子和，右子树的左叶子和，加起来就是整棵树的左叶子和，递归终止条件是当前节点没有叶子可探索了。左叶子和的计算则需要体现在父节点中，也就是“递归内部逻辑里”，由父节点判断左子树是否本质上是左叶子，是则累计结果。

完全二叉树的节点个数：
递归：利用完全二叉树可划分为数个满二叉树，而满二叉树极端向左向右遍历的最终深度一致的性质，快捷获取整棵满二叉树的内部节点个数，而无需老老实实递归到所有的叶子节点。

细节是：
1. 2^depth - 1的公式适用于将根节点记为深度1，
2. 而具体的代码计算则需要使用 << 右移运算符，对 1 << n 次就得到 2^n 次方，
3. 形象的理解就是 << 等价于指数加法，所以 1 << n <<==>> 2^(0+n)
耗时：2h

Junyuan Lu(陆俊元)

代码随想录算法训练营第十五天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和、222. 完全二叉树的节点个数

110. 平衡二叉树

257. 二叉树的所有路径

404. 左叶子之和

222. 完全二叉树的节点个数

今日收获