Python二叉树的深度

本文阅读 1 分钟
首页 Python笔记 正文

利用递归实现。如果一棵树只有一个结点,那么它的深度为1。递归的时候无需判断左右子树是否存在,因为如果该节点为叶节点,它的左右子树不存在,那么在下一级递归的时候,直接return 0。同时,记得每次递归返回值的时候,深度加一操作。

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

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 递归解法, 简单直接, 时间复杂度O(n), 空间复杂度O(logn)
    def TreeDepth(self, pRoot):
        if pRoot == None:
            return 0
        else:
            return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
    # 非递归算法,利用一个栈以及一个标志位栈
    def TreeDepth2(self, pRoot):
        if not pRoot:
            return 0
        depth = 0
        stack, tag = [], []
        pNode = pRoot
        while pNode or stack:
            while pNode:
                stack.append(pNode)
                tag.append(0)
                pNode = pNode.left
            if tag[-1] == 1:
                depth = max(depth, len(stack))
                stack.pop()
                tag.pop()
                pNode = None
            else:
                pNode = stack[-1]
                pNode = pNode.right
                tag.pop()
                tag.append(1)
        return depth
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python数字在排序数组中出现的次数
« 上一篇 01-21
Python判断平衡二叉树
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18087 篇
  • 评论总数:
    52244 条
  • 标签总数:
    8192 个
  • 总浏览量:
    15806946 次
  • 最后更新:
    2小时前

最多点赞

随便看看

标签TAG