(第29天)【leetcode题解】222、完全二叉树的节点个数 110、平衡二叉树 257、二叉树的所有路径

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

题目描述

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

思路

  1. 题目分析
  • 可以把完全二叉树分为两种情况:完全二叉树、满二叉树
  • 若是满二叉树:则向左递归和向右递归获得的深度一样;直接用公式2depth-1计算节点个数
  • 若是完全二叉树:向左向右递归知道遇到当前节点下的二叉树为满二叉树,然后根据公式计算节点个数后返回
  1. 递归法
  • 参数:root入口函数时代表根节点,递归中代表当前节点
  • 返回值:int返回节点个数
  • 终止条件:当前节点为空时,返回0;当前根节点所在二叉树为满二叉树时,用公式计算当前二叉树个数后返回。
  • 递归逻辑:左右中
  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;
        //判断以当前节点为根节点的二叉树是否为满二叉树
        //得到左子树深度
        while (left) {
            left = left->left;
            leftDepth++;
        }
        //得到右子树深度
        while (right) {
            right = right->right;
            rightDepth++;
        }
        if (rightDepth == leftDepth) {
            return (2 << leftDepth) - 1;//(2 << 1) 相当于2^2,因此leftDepth初始化为0;返回当前满二叉树的节点
        }
        //递归逻辑
        return countNodes(root->left) + countNodes(root->right) + 1;//左 右 中
    }
};

迭代法

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int sum = 0;
        while (!que.empty()) {
            int size = que.size();
            int num = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                num++;
            }
            sum += num;
        }
        return sum;
    }
};

110、平衡二叉树

题目描述

给定一个二叉树,判断它是否是 平衡二叉树

思路

  1. 题目分析
  • 判断二叉树是否为平衡二叉树:需要求以当前节点为根节点的树的左右子树的高度,然后比较它们之间的差是否大于1。
  1. 递归法
  • 参数:传入当前节点
  • 返回值:int,如果以当前节点为根节点的二叉树是平衡二叉树,则返回当前二叉树的最大高度;如果不是平衡二叉树,返回-1。
  • 终止条件:当前节点为空时,返回0;
  • 递归逻辑:后序遍历,左右中
  1. 迭代法
  • 定义一个函数:求传入节点的高度
  • 用栈模拟后序遍历:每个节点的高度就是以这个节点为根节点的树的最大深度
  • 用栈模拟后序遍历:遍历每一个节点,求出每一个节点左右子树的高度,若高度大于1则返回false;否则,返回true。

代码

递归法

class Solution {
public:
    int getHeight(TreeNode* cur) {
        if (cur == nullptr) return 0;
        int leftHeight = getHeight(cur->left);//左子树高度
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(cur->right);//右子树高度
        if (rightHeight == -1) return -1;
        //子树最大高度加1 == 当前树的最大高度
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

迭代法

class Solution {
public:
    //节点的高度就是以节点为根节点的二叉树的最大深度
    int getDepth(TreeNode* cur) {
        stack<TreeNode*> st;
        if (cur != nullptr) st.push(cur);
        int depth = 0;//记录深度
        int res = 0;//用来返回的最大深度,也就是高度
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != nullptr) {
                st.pop();
                st.push(node);
                st.push(nullptr);//标记
                depth++;
                if (node->right) st.push(node->right);//右
                if (node->left) st.push(node->left);//左 
            } else {
                st.pop();//去掉标记
                //node = st.top();//取出节点
                st.pop();
                depth--;
            }
            res = res > depth ? res : depth;
        }
        return res;
    }

    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == nullptr) return true;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) return false;
            if (node->right) st.push(node->right);//右
            if (node->left) st.push(node->left);//左
        }
        return true;
    }
};

257、二叉树的所有路径

题目描述

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

思路

** 递归法**:

  • 返回值:不需要返回值
  • 参数:cur代表当前节点,vector<int>类型的path用来存储路径上的节点,vector<string>类型的res用来当作路径结果返回。
  • 终止条件:遇到叶子节点。也就是cur->left == null && cur->right == null
  • 递归逻辑:前序遍历,中左右
  • 回溯逻辑:每一次递归返回后都是一次回溯,应该把回溯前(递归返回前)遍历到的节点取出

迭代法

  • 用前序遍历的方式来模拟遍历路径的过程。
  • 数据结构:一个栈用来存储遍历到的节点;一个栈用来存储同步遍历过程的路径(当遇到叶子节点时栈顶元素为一条最终可用的路径);一个vector<string>类型的容器来存储最终的路径结果集
  • 随着遍历过程,一个栈存储遍历的节点,一个栈同步存储一条路径。
  • 到达叶子节点的时候,栈中存储的路径已经是最终可用的一条路径,将这条路径加入结果集。
  • 遍历过程中回退时,存储节点的栈和存储路径的栈要同时取出栈顶元素,达到回退效果。

代码

递归法

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& path, vector<string>& res) {
        path.push_back(cur->val);//中
        
        //终止条件:遇到叶子节点
        if (cur->left == nullptr && cur->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 (cur->left) {
            traversal(cur->left, path, res);
            path.pop_back();//回溯
        }
        //右
        if (cur->right) {
            traversal(cur->right, path, res);
            path.pop_back();//回溯
        }
    }

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

迭代法

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> treeSt;//用来保存遍历的节点
        stack<string> pathSt;//用来保存一条路径,栈顶的元素是最终路径(根节点到当前节点的路径)
        vector<string> result;//用来保存路径集
        if (root == nullptr) return result;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top(); treeSt.pop();//取出节点   中
            string path = pathSt.top(); pathSt.pop();//取出该节点对应的路径
            //当前节点叶子节点,当前路径也是一条可用的路径
            if (node->left == nullptr && node->right == nullptr) {
                result.push_back(path);
            }
            //右
            if (node->right) {
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            //左
            if (node->left) {
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }
        return result;
    }
};

总结

  1. 节点的高度:从最下层节点到该节点的节点个数。
  2. 节点的深度:从根节点到该节点的节点个数。
  3. 求深度要从上往下查,用前序遍历(中左右)。
  4. 求高度要从下往上查,用后序遍历(左右中)。

最近更新

  1. react有什么特点

    2024-06-08 21:04:08       0 阅读
  2. Python内置函数pow()详解

    2024-06-08 21:04:08       0 阅读
  3. 【数据结构与算法】广度优先搜索(BFS)

    2024-06-08 21:04:08       0 阅读
  4. linux在文件夹中查找文件内容

    2024-06-08 21:04:08       0 阅读
  5. 自动化喷涂生产线控制方法概述

    2024-06-08 21:04:08       0 阅读
  6. Leetcode.2709 最大公约数遍历

    2024-06-08 21:04:08       0 阅读

热门阅读

  1. Jetpack compose中State和Kotlin Flow对比

    2024-06-08 21:04:08       6 阅读
  2. django支持https

    2024-06-08 21:04:08       5 阅读
  3. 如何反编译jar并修改后还原为jar

    2024-06-08 21:04:08       7 阅读
  4. nacos新版踩坑

    2024-06-08 21:04:08       5 阅读
  5. Openresty人机验证流程

    2024-06-08 21:04:08       6 阅读
  6. 【重学C语言】十九、SDL2 图形化编程的使用

    2024-06-08 21:04:08       4 阅读
  7. SWD端口无法连接如何排查

    2024-06-08 21:04:08       5 阅读
  8. 生物神经网络 原理分析研读02

    2024-06-08 21:04:08       6 阅读