以递归方式检索二叉树节点的深度

Question

任何人都可以指出在不使用递归的情况下在二叉树(不是平衡的树或BST)中获取节点深度的方法吗？理想情况下在Java/C/C#

该节点表示为:

class Node
{
  Node Left;
  Node Right;
  string Value;
  int Depth;
}

使用带有FIFO列表的Level Order是我的第一个想法,但是当我发现水平发生变化时,我很难过,特别是对于不平衡的树.

Answer 1

您可以使用堆栈实现任何resursive方法,这是resursion无论如何都可以工作的方式.想象一下你的resursive功能看起来像

function int getDepth (Node head, string val)
{
    if (head == NULL)
        return -1;

    if (val == head.Value)
        return head.Depth;

    return MAX(getDepth(head.Left, val), getDepth(head.Right, val);
}

非反复功能看起来像

function int getDepth (Node head, string val)
{
    Stack s = new Stack();

    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (s.Value == val)
                return s.Depth;
            else
            {
                s.push(temp.Left);
                s.push(temp.Right);
            }
        }

    }


    return -1;
}

编辑:

此函数设置每个节点的深度

function void setDepth (Node head)
{
    Stack s = new Stack();

    head.Depth = 0;
    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (temp.Left != NULL)
            {
                temp.Left.Depth = temp.Depth + 1;
                s.push(temp.Left);
            }

            if (temp.Right != NULL)
            {
                temp.Right.Depth = temp.Depth + 1;
                s.push(temp.Right);
            }
        }

    }

}

Answer 2

我假设你的意思是填充节点上的深度值,和/或找到最大深度.一种方法是使用两个列表,并按照建议执行级别顺序.它类似于:

int level=0;
List<Node> currentLevel = new List<Node>{root};
while(currentLevel.Count != 0)
{
  List<Node> nextLevel = new List<Node>{};
  foreach(Node node in currentLevel)
  {
    if(node.Right!=null) nextLevel.Add(node.Right);
    if(node.Left != null) nextLevel.Add(node.Left);
    node.Depth=level;
  }
  level++;
  currentLevel=nextLevel;
}

基本上,您枚举给定级别上的每个节点,然后在下一级别找到每个节点; 直到你用完节点/级别.显然,List可以替换为任何列表,如数据结构(链接列表,队列等).而"水平"的最后一个值将是最大深度+1.我怀疑.

另一个基于重新阅读问题的澄清; 如果要搜索具有特定值的节点,并且想要查找其深度,则可以将foreach循环更改为包含"if(node.Value == searchValue)返回级别".而且,从技术上讲,如果要搜索特定值,则不应该进行级别顺序遍历,而应使用相关二叉树属性搜索值(例如val <currentNode.Value goto left else goto right),并跟踪你的深度.如果您只获得节点并想要查找其深度,则需要从根执行二进制搜索节点,或者您需要跟踪节点的父节点.