查找二叉树中节点的深度不是BST

我有一个二叉树而不是bst，我需要找到该二叉树中某个节点的深度有没有其他方法可以实现除了使用某些稀释度计的水平顺序遍历以主要计数水平。查找二叉树中节点的深度不是BST

作为输入，我有树的根节点和我需要找到深度的树的节点之一。

我希望有一些递归的方式来找到这个

来源

2011-11-23 Ashish Sharma

家庭作业问题？ –

如果你不想做一个BFS你可以做一个DFS（你也可以做到这一点递归）。

来源

2011-11-23 18:40:47

可以请你给我一些示例代码使用递归来找到这个.. –

由于你的问题似乎真的是一个家庭作业的问题，我强烈建议你看看你最喜欢的搜索引擎如何DFS的作品。 –

由于树不是BST，最坏的复杂度将是O（n）。因此，任何类型的遍历（pre，post，in）都会帮助您将当前节点与输入节点进行比较。所有这些遍历都使用递归。 –

尝试在递归函数中传递一个附加参数来指示深度。

来源

2011-11-24 07:33:54 kaustubh

不需要额外的参数，您可以简单地使用函数的返回值。 –

DFS函数的伪代码，第一次调用将是DFS(root)。

DFS(node v, integer d) 
    visited[v] = true 
    depth[v] = d 

    for each u such that u is adjacent to v 
    if visited[u] == false 
     DFS(u, d+1)

来源

2011-11-24 10:08:33

您不需要访问（非循环）也不需要深度变量（因为您只需查找一个值，不需要遍历每个节点）。 –

查找二叉树中节点的深度不是BST

回答

相关问题