当前位置： 首页 > article >正文

DAY15|二叉树Part03|LeetCode: 222.完全二叉树的节点个数、110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

article 2024/11/1 4:11:22

目录

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

基本思路

普通二叉树

完全二叉树

C++代码

LeetCode: 110.平衡二叉树

基本思路

C++代码

LeetCode: 257. 二叉树的所有路径

基本思路

C++代码

LeetCode: 404.左叶子之和

基本思路

C++代码

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

力扣代码链接

文字讲解：LeetCode: 222.完全二叉树的节点个数

视频讲解：要理解普通二叉树和完全二叉树的区别！

基本思路

        对于本题来讲，可以将其视为普通二叉树求解也可以单独考虑完全二叉树的情况来求解。

普通二叉树

作为普通二叉树，可以使用递归法进行求解，也可以考虑通过层序遍历，一层层统计出二叉树节点数量，下面以递归法为例：

  • 确定递归函数的参数和返回值

        传入的是根节点，返回该节点为二叉树的根节点的节点数量，为int类型。

int getNodesNum(TreeNode* cur) {
  • 确定终止条件

        当节点为空时，说明包含的节点数为零，返回0。

if (cur == NULL) return 0;
  • 确定单层递归逻辑

        先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

int leftNum = getNodesNum(cur->left);      // 左
int rightNum = getNodesNum(cur->right);    // 右
int treeNum = leftNum + rightNum + 1;      // 中
return treeNum;

完全二叉树

        首先，明确什么是完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

        完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

        对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

        对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

  • 确定递归函数的参数和返回值

传入的是根节点，返回该节点为二叉树的根节点的节点数量，为int类型。

int countNodes(TreeNode* root) {
  • 确定终止条件

当节点为空时，说明节点数量为0，返回0，然后需要对当前子树是否为满二叉树进行判断，因为满二叉树一定是完全二叉树，而满二叉树的节点数量很好计算，为2^n-1,其中n为二叉树的深度。

此时可以记录并根据左深度和右深度来判断子树是否为满二叉树，如果相等，则说明是当前子树为满二叉树，直接返回二叉树的节点数量2^左深度-1。

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，返回满足满二叉树的子树节点数量
}
  • 确定单层递归逻辑

        如果左深度和右深度不相等，则继续递归，记录左子树的节点数量和右子树的节点数量，最后加1（根节点）即为完全二叉树的节点数量。

int leftTreeNum = countNodes(root->left);       // 左
int rightTreeNum = countNodes(root->right);     // 右
int result = leftTreeNum + rightTreeNum + 1;    // 中
return result;

C++代码

// 普通二叉树
class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == NULL) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};


//完全二叉树
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
        }
        int leftTreeNum = countNodes(root->left);       // 左
        int rightTreeNum = countNodes(root->right);     // 右
        int result = leftTreeNum + rightTreeNum + 1;    // 中
        return result;
    }
};

LeetCode: 110.平衡二叉树

力扣代码链接

文字讲解：LeetCode: 110.平衡二叉树

视频讲解：后序遍历求高度，高度判断是否平衡

基本思路

        一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。对于求高度，我们应该选择后序遍历，因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。

        使用递归法步骤如下：

  • 确定递归函数的参数和返回值

        参数为当前传入的节点，返回值为当前节点的高度，为int类型。其中如果子树不是平衡二叉树，我们就向中间节点传入-1，并最终传到根节点。

// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)
  • 确定终止条件

        递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

if (node == NULL) {
    return 0;
}
  • 确定单层递归逻辑

        分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) return -1;

int result;
if (abs(leftHeight - rightHeight) > 1) {  // 中
    result = -1;
} else {
    result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}

return result;

C++代码

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        int result;
        if (abs(leftHeight - rightHeight) > 1) {  // 中
            result = -1;
        } else {
            result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
        }

        return result;
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

LeetCode: 257. 二叉树的所有路径

力扣代码链接

文字讲解：LeetCode: 257. 二叉树的所有路径

视频讲解：递归中带着回溯，你感受到了没？

基本思路

        这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

        在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

依旧使用递归的方法进行求解：

  • 确定递归函数的参数和返回值。

        需要传入的参数为根节点，并且记录所搜索的路径，以及将搜索到的路径结果保存在变量result中。

void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
  • 确定终止条件

        和前面的题目不同，不再是节点为空时停止，因为当搜索到叶子节点时，就需要将路径记录在result中，即cur指针指向的节点不为空，但是左右孩子为空。而根据题目要求节点之间需要用->进行连接，因此需要对路径中的节点进行遍历，并加入->。

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点
    string sPath;
    for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式
        sPath += to_string(path[i]);
        sPath += "->";
    }
    sPath += to_string(path[path.size() - 1]); // 记录最后一个节点（叶子节点）
    result.push_back(sPath); // 收集一个路径
    return;
}
  • 确定单层递归逻辑

        因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。如果和之前的题目中的顺序一样，当节点的左右孩子都为空时，就直接返回路径，此时就不会包含叶子结点。

path.push_back(cur->val);

        而我们在进行递归之后，需要进行回溯。

if (cur->left) {
    traversal(cur->left, path, result);
    path.pop_back(); // 回溯
}
if (cur->right) {
    traversal(cur->right, path, result);
    path.pop_back(); // 回溯
}

C++代码

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;
    }
};

LeetCode: 404.左叶子之和

力扣代码链接

文字讲解：LeetCode: 404.左叶子之和

视频讲解：二叉树的题目中，总有一些规则让你找不到北

基本思路

        最重要的是要确定二叉树中哪些节点是左叶子，如果一个节点的左右孩子为空，那么我们就可以认为这个节点是叶子节点，那么在这个基础上进行延伸，如果一个节点有左孩子，并且左孩子的左右孩子都为空，那么这个节点的左孩子不就是所谓的左叶子节点了吗？

使用递归法进行求解：

  • 确定递归函数的参数和返回值。

首选我们需要传入根节点，返回的是左叶子节点的和，为int类型。

int sumOfLeftLeaves(TreeNode* root)
  • 确定终止条件

        对二叉树的所有节点进行遍历，如果节点为空时，就返回零，说明此时不存在左叶子节点。但是我们如果遍历的节点为叶子节点时（包括左右叶子节点）我们应该怎么办呢？这个时候我们同样返回0（因为此时还不能确定是左叶子节点还是右叶子节点，我们必须看叶子节点是否为其父节点的左孩子）。

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;

C++代码

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;
    }
};

http://www.kler.cn/a/373901.html

相关文章：

  • JavaScript语法基础——变量，数据类型，运算符和程序控制语句（小白友好篇，手把手教你学会！）
  • 拍拍贷鸿蒙版H5容器之路
  • windows系统命令讲解
  • ubuntu交叉编译expat库给arm平台使用
  • 瓦片与数据使用要素服务的区别
  • etcd 备份还原
  • 江协科技STM32学习- P26 UART串口外设
  • 普通人的核心竞争力
  • 《Python游戏编程入门》注-第4章2
  • Unity XR Interaction Toolkit 开发教程（1）：OpenXR 与 XRI 概述【3.0 以上版本】
  • 第13次CCF CSP认证真题解
  • 【GO学习笔记 go基础】访问控制
  • 我谈Canny算子
  • leetcode双指针题目总结
  • SAP B1 功能模块字段介绍 - 价格清单（上）
  • Flutter动画渐变
  • Java面试经典 150 题.P169. 多数元素（005）
  • java.sql.SQLException: ORA-00971: 缺失 SET 关键字
  • 瑞格智慧心理服务平台 NPreenSMSList.asmx sql注入漏洞复现
  • Python 从入门到实战43（Pandas数据结构）
  • Ika赋予Sui开发者与其他链交互的能力
  • Java | Leetcode Java题解之第517题超级洗衣机
  • 如何实现易快报合同付款申请单对接金蝶云星空
  • python 模块和包、类和对象
  • 【JSON改】同结构JSON的批量修改工具
  • 高并发设计模式之ForkJoin模式