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

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出去,这就是回溯。

定义递归函数:

  1. 传入参数:
    a. TreeNode *node:传入一个节点。
    b. vector<int> path:通过一个path来记录沿途的路径,便于之后的回溯。
    c. vector<string> res:用来记录最终结果。
  2. 返回值:没有返回值,递归的结果在res中存放。
  3. 终止条件:当该节点的左孩子和右孩子都为nullptr时,递归终止。
  4. 递归思路:采用前序遍历,先将节点压入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;
    }
};

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