「代码随想录算法训练营」第十三天 | 二叉树 part3

2024-07-17 16:47 由云雀AC了一整天发表于 #其他

110. 平衡二叉树

题目链接：https://leetcode.cn/problems/balanced-binary-tree/
题目难度：简单
文章讲解：https://programmercarl.com/0110.平衡二叉树.html
视频讲解：https://www.bilibili.com/video/BV1Ug411S7my
题目状态：通过

思路：

采用递归的方式，遍历每个节点的左右孩子的深度以及其之间的深度差是否超过 1，如果超过 1 的话，就直接返回false，直到遍历结束。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int isBalancedUtil(TreeNode *root, int &balanced) {
        if(root == nullptr) return 0;
        int leftHeight = isBalancedUtil(root->left, balanced);
        if(balanced == 0) return 0;
        int rightHeight = isBalancedUtil(root->right, balanced);
        if(balanced == 0) return 0;
        if(abs(leftHeight - rightHeight) > 1) balanced = 0;
        return max(leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode* root) {
        int balanced = 1;
        isBalancedUtil(root, balanced);
        return balanced;
    }
};

代码随想录提供了一种更好的代码：

class Solution {
public:
    int getHeight(TreeNode *node) {
        if(node == nullptr) return 0;
        int leftHeight = getHeight(node->left);
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if(rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : (max(leftHeight, rightHeight) + 1);
    }
    bool isBalanced(TreeNode *root) {
        return getHeight(root) == -1 ? false : true;
    }
};

257. 二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/
题目难度：简单
文章讲解：https://programmercarl.com/0257.二叉树的所有路径.html
视频讲解：https://www.bilibili.com/video/BV1ZG411G7Dh
题目状态：一点思路也没有

学习思路：

学习回溯，看下图

回溯和递归是不分开的，当每次进行递归的时候将之前保存的路径中的节点pop出去，这就是回溯。

定义递归函数：

传入参数：
a. TreeNode *node：传入一个节点。
b. vector<int> path：通过一个path来记录沿途的路径，便于之后的回溯。
c. vector<string> res：用来记录最终结果。
返回值：没有返回值，递归的结果在res中存放。
终止条件：当该节点的左孩子和右孩子都为nullptr时，递归终止。
递归思路：采用前序遍历，先将节点压入path中，再判断其左右孩子是否都为nullptr（此时为递归结束，即该节点为叶子节点），若不为nullptr，分别将其左右孩子（不为空的那个）进入递归，此时将path中该节点pop出来（这个就是回溯）。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void backtracking(TreeNode *node, vector<int> &path, vector<string> &res) {
        // 中
        path.push_back(node->val);
        // 终止条件
        if(node->left == nullptr && node->right == nullptr) {
            string sPath;
            for(int i = 0; i < path.size() - 1; ++i) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            res.push_back(sPath);
            return;
        }
        // 左
        if(node->left) {
            backtracking(node->left, path, res);
            path.pop_back();
        }
        // 右
        if(node->right) {
            backtracking(node->right, path, res);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        vector<int> path;
        if(root == nullptr) return res;
        backtracking(root, path, res);
        return res;
    }
};

404. 左叶子之和

题目链接：https://leetcode.cn/problems/sum-of-left-leaves/
题目难度：简单
文章讲解：https://programmercarl.com/0404.左叶子之和.html
视频讲解：https://www.bilibili.com/video/BV1GY4y1K7z8
题目状态：通过

个人思路：

定义一个int类型变量leftSum，用来存储结果使用层序遍历，当遍历到该节点的左孩子时，若其左孩子没有左孩子和右孩子（即该节点的左孩子为叶子节点），将其值加入leftSum中。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode *> que;
        if(root == nullptr) return 0;
        int leftSum = 0;
        que.push(root);
        while(!que.empty()) {
            TreeNode *node = que.front();
            que.pop();
            if(node->left) {
                que.push(node->left);
                if(node->left->left == nullptr && node->left->right == nullptr) leftSum += node->left->val;
            }
            if(node->right) que.push(node->right);
        }
        return leftSum;
    }
};

递归思想的代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) 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);
        // 这里面leftValue代表左孩子的左叶子节点值之和，rightValue代表右孩子的左叶子节点值之和
        int sum = leftValue + rightValue;
        return sum;
    }
};

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

题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/
题目难度：简单
文章讲解：https://programmercarl.com/0222.完全二叉树的节点个数.html
视频讲解：https://www.bilibili.com/video/BV1eW4y1B7pD
题目状态：通过

思路：

层序遍历，加个计数sum。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode *> que;
        if(root == nullptr) return 0;
        que.push(root);
        int sum = 1;
        while(!que.empty()) {
            TreeNode *node = que.front();
            que.pop();
            if(node->left) {
                que.push(node->left);
                sum++;
            }
            if(node->right) {
                que.push(node->right);
                sum++;
            }
        }
        return sum;
    }
};

递归方法：（利用完全二叉树的特性，2的深度次方-1，这样只需要遍历完全二叉树的左孩子和右孩子最边上的节点即可）

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

热门相关：我写的书实在太毒了超级英雄全能千金燃翻天血战天下聊斋大圣人