迭代地查找二叉树中元素的高度

Question

如何求二叉树中元素的高度？在迭代方法中。

如果在下面的二叉树中元素为 22，则其高度为 2。我是否应该先找到二叉树的高度，然后从该高度开始，当我向下移动一个节点时，递减它？

如果您有答案，请随意用伪代码或您想要的任何编程语言编写它。谢谢。

Answer 1

对树做层序遍历，留一个变量跟踪当前节点的深度

树的高度将是最深节点的深度。
如果找到要查找的节点，请将其存储在变量中
最后用树的高度减去节点的深度

代码：

class BinaryTreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def setChildren(self, left, right):
        self.left = left
        self.right = right

def heightOfNode(root, searchValue):
    queue, depth, maxDepth = [], None, 0
    if (root != None):
        queue.append((root, 1))
        maxDepth = 1
    while len(queue) > 0:
        node, nodeDepth = queue.pop(0)
        if (node.left != None):
            queue.append((node.left, nodeDepth + 1))
        if (node.right != None):
            queue.append((node.right, nodeDepth + 1))
        if (node.val == searchValue):
            depth = nodeDepth
        maxDepth = max(nodeDepth, maxDepth)
    return maxDepth - depth

if __name__=='__main__':
    node14 = BinaryTreeNode(14)
    node22 = BinaryTreeNode(22)
    node2 = BinaryTreeNode(2)
    node1 = BinaryTreeNode(1)
    node5 = BinaryTreeNode(5)
    node20 = BinaryTreeNode(20)
    node30 = BinaryTreeNode(30)
    node4 = BinaryTreeNode(4)
    node17 = BinaryTreeNode(17)
    node50 = BinaryTreeNode(50)
    node40 = BinaryTreeNode(40)

    node14.setChildren(node2, node22)
    node2.setChildren(node1, node5)
    node22.setChildren(node20, node30)
    node5.setChildren(node4, None)
    node20.setChildren(node17, node50)
    node30.setChildren(None, node40)

    print(heightOfNode(node14, 22))

输出：

迭代地查找二叉树中元素的高度

Find the height of an element in a binary tree, iteratively

algorithm

binary-tree

graph-algorithm

data-structures