剑指Offer（三十八）：二叉树的深度

2018年1月16日11:27:42 5 9,426 °C
摘要

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

剑指Offer（三十八）：二叉树的深度

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

这道题蛮简单的，求二叉树的深度。可以是递归的方法，属于DFS（深度优先搜索）；另一种方法是按照层次遍历，属于BFS（广度优先搜索）。

2、代码

C++：

DFS方法：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot == NULL){
            return 0;
        }
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        return (left > right) ? (left + 1) : (right + 1);
    }
};

BFS方法：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot == NULL){
            return 0;
        }
        queue<TreeNode*> que;
        int depth = 0;
        que.push(pRoot);
        while(!que.empty()){
            int size = que.size();
            depth++;
            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);
                }
            }
        }
        return depth;
    }
};

感谢@小小毛提供的本地测试用例：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    def TreeDepth(self, root):
        # write code here
        if root is None:
            return 0
        left=self.TreeDepth(root.left)
        right=self.TreeDepth(root.right)
        print(left,right)
        return max(left,right)+1
 
if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
 
    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A4.left=A6
 
    solution=Solution()
    ans=solution.TreeDepth(A1)
    print('ans=',ans)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：5   其中：访客  3   博主  2

    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
      回复 2019年4月10日 下午3:16  沙发

      大家好，我是小小渣。渣渣最理解渣渣啦。Python实现加测试。
      class TreeNode:
      def __init__(self, x):
      self.val = x
      self.left = None
      self.right = None

      class Solution:
      def TreeDepth(self, root):
      # write code here
      if root is None:
      return 0
      left=self.TreeDepth(root.left)
      right=self.TreeDepth(root.right)
      print(left,right)
      return max(left,right)+1

      if __name__==’__main__’:
      A1 = TreeNode(1)
      A2 = TreeNode(2)
      A3 = TreeNode(3)
      A4 = TreeNode(4)
      A5 = TreeNode(5)
      A6 = TreeNode(6)

      A1.left=A2
      A1.right=A3
      A2.left=A4
      A2.right=A5
      A4.left=A6

      solution=Solution()
      ans=solution.TreeDepth(A1)
      print(‘ans=’,ans)

        • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
          回复 2019年4月10日 下午3:48  1层

          @小小毛 万分感谢，已加入文章～

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
          回复 2019年4月10日 下午4:24  板凳

          小小渣，突然觉得之所以有些地方困很久，貌似是递归理解的不是很好，在此打个卡，赞个路人源，希望找到实习 :razz: 。此外，@本站博主，评论部分，提交代码不是很方便啊。建议添加markdown模块。 :oops:
          什么是递归算法呢？
          递归：递归在程序中指的是函数对自身的调用，它的主要思想是把一个大型的问题逐层分解为与原问题相似的较小的问题来求解，即把大问题转变为性质相同的小问题的重复计算。递归的核心思想是“递”和“归”，通俗地可以理解为有“递去”有“回归”（有去有回），一直往下“递去”，知道满足一个临界条件，然后逐步“归来”。
          对于这一题重复的一件事是分别找左子树和右子树。

            • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
              回复 2019年4月10日 下午5:01  1层

              @小小毛 加油，现在互联网行情不太乐观，但是努力会有收获的。添加md需要再开发了，有时间添加下，感谢～

            • avatar Dejavu 来自天朝的朋友 搜狗浏览器 Windows 8.1 天津市 天津大学 2
              回复 2019年4月17日 下午7:01  地板

              只有一个非空根节点深度是1吗？

              感觉说成路径上的节点数会比路径合适