day17 | 110.平衡二叉树、 257. 二叉树的所有路径、 404.左叶子之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了day17 | 110.平衡二叉树、 257. 二叉树的所有路径、 404.左叶子之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接

题目链接：

https://leetcode.cn/problems/balanced-binary-tree/

https://leetcode.cn/problems/binary-tree-paths/

解题及思路学习

110. 平衡二叉树

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

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

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

示例 1：

!https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg

输入：root = [3,9,20,null,null,15,7]
输出：true

思考：跟之前求数的高度差不多。判断两颗子树的高度绝对值是否不超过1.先用递归试试。

递归思路代码：

递归中嵌套了递归，代码时间复杂度直接拉满。

class Solution {
public:
    int maxHeight(TreeNode* root) {
        if (root == NULL) return 0;
        int leftHeight = maxHeight(root->left);
        int rightHeight = maxHeight(root->right);
        int result = 1 + max(leftHeight, rightHeight);
        return result;
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;

        bool leftBalance = isBalanced(root->left);
        bool rightBalance = isBalanced(root->right);

        int left = maxHeight(root->left);
        int right = maxHeight(root->right);

        if ( abs(left - right) <= 1 && leftBalance && rightBalance) return true;
        return false;
    }
};

随想录：求解高度用后序遍历，求解深度用前序遍历。

class Solution {
public:
		// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* root) {
        if (root == NULL) return 0;

        int left = getHeight(root->left);
        if (left == -1) return -1;
        int right = getHeight(root->right);
        if (right == -1) return -1;

        if (abs(left - right) > 1) return -1;
        int result = max(left, right) + 1;
        return result;
    }

    bool isBalanced(TreeNode* root) {
        if (getHeight(root) != -1) return true;
        return false; 
    }
};

257. 二叉树的所有路径

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

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

示例 1：

!https://assets.leetcode.com/uploads/2021/03/12/paths-tree.jpg

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

思考：可以用一个二维vector容器来记录每个所有根节点到叶子节点的路径。其中每一条数据代表一条数据。

随想录：需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 
        // 这才到了叶子节点
        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;
    }
};

vector::pop_back() 是"vector" 头文件的库函数，用于从vector 尾部删除一个元素，从vector 后面删除元素并返回void。

这道题目中，因为要使用path来记录所有路径，但是只有一个内存地址，所以，当遍历下一个节点时，需要把前面节点进行释放，所以需要pop_back()操作。

404.左叶子之和

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

示例 1：

!https://assets.leetcode.com/uploads/2021/04/08/leftsum-tree.jpg

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

思考：这题可以用后续递归遍历，先统计左右子树的左叶子之和。

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

        int result = 0;
        if (root->left && root->left->left == NULL && root->left->right == NULL) {
            result += root->left->val;
        }
        return result + right + left;
    }
};

好像层序遍历也能行，只需要判断一下是否为左叶子。

随想录：减少了一层递归。并且在左边返回的数值那里更清楚了。左边节点只要时左叶子节点，那就只返回该节点的值就行。它后面不会有其他节点。如果不是，则该节点一定不会是叶子节点，所以只需要直接用left值就行。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0; 
        if (root->left == NULL && root->right ==NULL) return 0;   //当为左叶子节点的时候返回0，减少一层

        int left = sumOfLeftLeaves(root->left);
        if (root->left && root->left->left == NULL && root->left->right == NULL) {
            left = root->left->val;
        }
        int right = sumOfLeftLeaves(root->right);
        return left + right;
    }
};