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

本文主要是介绍(第29天)【leetcode题解】222、完全二叉树的节点个数 110、平衡二叉树 257、二叉树的所有路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 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. 求高度要从下往上查,用后序遍历(左右中)。

这篇关于(第29天)【leetcode题解】222、完全二叉树的节点个数 110、平衡二叉树 257、二叉树的所有路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1042852

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L