时间戳

首页 > 解决方案 > 如何找到二叉树中特定节点的深度？

python - 如何找到二叉树中特定节点的深度？

问题描述

我正在尝试找出解决此问题的递归解决方案。主要是返回节点所在的二叉树中的级别。

def find_depth(tree, node):
    if node == None:
        return 0 
    else: 
        return max(find_depth(tree.left))
        #recursive solution here

将此类用于值：

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left  = left
        self.right = right

示例：调用find_depth(tree, 7)应返回 7 在树中的级别。（2级）

   3
  / \
  7  1  <------ return that 7 is at level 2
 / \  
 9 3

标签： pythonrecursionbinary-tree

解决方案

递归是一种函数式遗产，因此将其与函数式风格一起使用会产生最佳结果 -

  1. 基本情况：如果输入tree为空，我们无法搜索，返回None结果
  2. 归纳，输入不tree为空。如果匹配搜索，返回当前深度，tree.datavalued
  3. 归纳，输入不tree为空tree.data且不匹配。返回的递归结果或递归结果tree.leftfind.right
def find (t = None, value = None, d = 1):
  if not t:
    return None              # 1
  elif t.value == value:
    return d                 # 2
  else:
    return find(t.left, value, d + 1) or find(t.right, value, d + 1) # 3

class tree:
  def __init__(self, value, left = None, right = None):
    self.value = value
    self.left = left
    self.right = right

t = tree \
  ( 3
  , tree(7, tree(9), tree(3))
  , tree(1)
  )

print(find(t, 7)) # 2
print(find(t, 99)) # None

你也可以在你的类中实现该find方法tree

def find (t = None, value = None, d = 1):
  # ...

class tree
  def __init__ #...

  def find(self, value)
    return find(self, value)

print(t.find(7)) # 2
print(t.find(99)) # None

推荐阅读