• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

面试题55-I:二叉树的深度(C++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目地址:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

题目描述

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

题目示例

例如:

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

解题思路

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

DFS(深度优先搜索-递归):深度优先搜索方法常常采用递归或者栈的方法实现,在这里我们使用递归的方法解决,直接返回树的深度等于左子树和右子树之中的最大值+1,即h = max(maxDepth(root->letf), maxDepth(root->right) + 1。二叉树的深度计算方法如下

  • 如果二叉树为一个节点,则二叉树深度h=1
  • 如果二叉树没有左子树,则二叉树深度h=右子树深度+1,反之,如果二叉树没有右子树,则二叉树深度h=左子树深度+1
  • 如果二叉树既有左子树又有右子树,则则二叉树深度h=max(左子树深度,右子树深度)+1

DFS(深度优先搜索-非递归-栈):中序遍历顺序为”左子树->根节点->右子树“,在这里我们使用中序遍历方法找到二叉树的最大深度,从根节点开始,此时并不需要将根节点入栈,先遍历左子树,将左子树所有元素入栈之后,再将根节点入栈,最后,右子树入栈。

BFS(广度优先搜索):广度优先搜索方法常采用队列来实现,遍历队列中的各节点,并将其左子节点和右子节点分别加入队列。然后,对二叉树一层一层遍历,每遍历一层,深度加1。

程序源码

DFS(递归)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
    
return max(maxDepth(root->left), maxDepth(root->right)) + 1; } };

DFS(非递归-栈)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        stack<pair<TreeNode*, int>> s;
        int deep = 0, cur_deep = 0;
        TreeNode* p = root;
        while(!s.empty() || p != nullptr) //若栈非空,则表示还有一些元素的右子树未访问,若p非空,则说明还有一些元素的左子树未访问,
        {
            while(p != nullptr)
            {
                s.push(pair<TreeNode*, int>(p, ++cur_deep)); //一直往左子树走,直到叶子节点
                p = p->left;
            }
            p = s.top().first;
            cur_deep = s.top().second;
            if(cur_deep > deep) deep = cur_deep;
            s.pop();
            p = p->right;
        }
        return deep;
    }
};

BFS(队列)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while(!que.empty()) //队列不为空,表示还有元素未访问
        {
            depth++;
            int cur_len = que.size();
            for(int i = 0; i < cur_len; i++) //一个for循环表示一层
            {
                TreeNode* curNode = que.front();
                que.pop();
                if(curNode->left != nullptr) que.push(curNode->left);
                if(curNode->right != nullptr) que.push(curNode->right);
            }
        }
        return depth;
    }
};

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#属性默认值设置发布时间:2022-07-13
下一篇:
C语言之基本算法26—佩尔方程求解发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap