剑指offer:二叉树的深度

傷城~ 2022-04-10 09:15 303阅读 0赞

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

AC C++ Solution:

递归

  1. class Solution {
  2. public:
  3.     int TreeDepth(TreeNode* pRoot)
  4.     {
  5.         if(pRoot == NULL)
  6.             return 0;
  8.         return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right)) + 1;
  9.     }
  10. };

非递归：

  1. class Solution {
  2. public:
  3.     int TreeDepth(TreeNode* pRoot)
  4.     {
  5.         if(pRoot == nullptr)
  6.             return 0;
  8.         queue<TreeNode*> q;
  9.         q.push(pRoot);
  10.         int level = 0;
  12.         while(!q.empty()) {
  13.             int n = q.size();
  14.             level++;
  15.             while(n--) {
  16.                 TreeNode* node = q.front();
  17.                 q.pop();
  19.                 if(node->left)
  20.                     q.push(node->left);
  21.                 if(node->right)
  22.                     q.push(node->right);
  23.             }
  24.         }
  26.         return level;
  27.     }
  28. };

发表评论

表情：
评论列表 （有 0 条评论，303人围观）

还没有评论，来说两句吧...

相关阅读

    相关 剑指offer 二叉树的深度

    [剑指offer题型分类及各题的代码及解题思路][offer] 1、题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树...

    Dear 丶Dear 丶/ 0 赞/ 166 阅读

    相关 剑指Offer | 二叉树的深度

    一、题目 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 二、思路 (1) 递归的思想适合

    短命女短命女/ 0 赞/ 250 阅读

    相关 剑指offer:二叉树的深度

    题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 AC C++ Solution:

    傷城~傷城~/ 0 赞/ 304 阅读

    相关 剑指Offer-二叉树的深度

    题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路—使用堆栈：使用堆栈依次压入

    布满荆棘的人生布满荆棘的人生/ 0 赞/ 263 阅读