如何查找並返回二叉樹的最底部（最深節點）節點？二叉搜索樹？

Question

我有一個binary tree，唯一的條件是最深層次中有一個節點。樹中的節點具有父屬性（以及左側，右側，數據）

是否有可能確定最深層次的節點比O(N更好？ 如果樹是binary search tree (right->data > parent->data, left->data < parent->data)而不是二叉樹，該怎麼辦？

我可以使用廣度優先的方法，它可以在二叉樹和二叉搜索樹的O（N）中完成工作，但想知道是否有更好的方法。

Answer 1

即使有一個平衡樹，你必須檢查每個子樹找到最深的節點，如：

struct RESULT{ 
    Node *node; 
    int level; 
}; 
RESULT getDeepest(Node *root){ 
    if(root == NULL){ 
     RESULT result = {NULL, 0}; 
     return result; 
    } 
    RESULT lResult = getDeepest(root->left); 
    RESULT rResult = getDeepest(root->right); 
    RESULT result = lResult.level < rResult.level ? rResult : lResult; 
    ++ result.level; 
    if(result.node == NULL) 
     result.node = root; 
    return result; 
} 

Answer 2

沒有辦法做得比O(n)更好。

當所有節點只剩下孩子時，考慮一棵樹 - 您需要掃描所有節點才能找到最深的節點。

Answer 3

public Node deepestNode(Node root, int level){ 
     int deepestLevel=0; 
     Node deepestNode=null; 
     if(root==null){ 
      return null; 
     } 
     deepestNode(root.left,level++); 
     if(level>deepestLevel){ 
      deepestLevel=level;`` 
      deepestNode =root; 
     } 
     deepestNode(root.right,level++);//not sure of increment 
     return deepestNode; 
    }