以不同的方式計算BST的深度

Question

如果要在沒有任何參數的情況下聲明它，您將如何計算BST的深度？我知道你能做到像參數如下：

public class BST { 
    public int maxDepth(TreeNode root) { 
     if(root==null) return 0; 
     int left=maxDepth(root.left); 
     int right=maxDepth(root.right); 
     return Math.max(left,right)+1; 
    } 

} 

但有可能做到這一點不帶參數如下：

public int maxDepth(){} 

只要我們能夠訪問根和其左右的孩子從內部的BST的方法？

Answer 1

與問題一點信息和多種猜測：

public int maxDepth() { 
     return maxDepth(root); 
    } 

的其餘代碼：

public class BST { 
    public int maxDepth() { 
     return maxDepth(root); 
    } 

    public int maxDepth(final TreeNode root) { 
     if (root == null) 
      return 0; 
     final int left = maxDepth(root.left); 
     final int right = maxDepth(root.right); 
     return Math.max(left, right) + 1; 
    } 

    public TreeNode root; 

    public static class TreeNode { 
     public TreeNode left, right; 
    } 
} 

Answer 2

你問到一個遞歸算法改寫爲迭代形式。

一般的解決方案是一個堆棧。

在這種情況下，我們使用堆棧來跟蹤當前節點。我們通過將currentNode放置到parent堆棧來遍歷樹。這使得當前節點成爲parent.peek()。

我們需要的第二個信息是，如果我們逐層遍歷樹，那麼接下來要訪問哪個節點。爲此，我們使用第二個堆棧（它代表了函數的內部狀態）。第二個堆棧存儲下一步（左，右，下）。

看起來很複雜，但我們必須手工做一些東西，它隱藏在任何編程語言的函數堆棧中。 Stack.pop對應於函數返回。 Stack.push爲下一次迭代準備參數。

我們結束與下面的程序：

import java.util.Stack; 

public class BST { 

    static class TreeNode { 
     TreeNode right, left; 
    } 

    TreeNode root; 

    static final int LEFT = 1; 
    static final int RIGHT = 2; 
    static final int UP = 3; 

    public int maxDepth() { 

     if (root == null) 
      return 0; 

     Stack<TreeNode> parent = new Stack<>(); 
     Stack<Integer> nextTurn = new Stack<>(); 

     int max = 0; 

     parent.push(root); // parent.peek() is the currentNode. 
          // parent.size() is the current depth 
     nextTurn.push(LEFT); 
     while (!parent.isEmpty()) { 
      switch (nextTurn.pop()) { 
      case LEFT: // descend left (both subtrees left) 
       nextTurn.push(RIGHT); 
       if (parent.peek().left != null) { 
        parent.push(parent.peek().left); 
        nextTurn.push(LEFT); 
       } 
       break; 
      case RIGHT: // descend right (left subtree done) 
       nextTurn.push(UP); 
       if (parent.peek().right != null) { 
        parent.push(parent.peek().right); 
        nextTurn.push(LEFT); 
       } 
       break; 
      case UP: // go up (both subtrees done) 
       if (parent.peek().left == null && parent.peek().right == null) { 
        // counting happens here. 
        // we are leaving a leaf node. 
        max = Math.max(max, parent.size()); 

       } 
       parent.pop(); 
       break; 
      } 

     } 
     return max; 
    } 

    public static void main(String[] args) { 
     // small test: 
     BST me = new BST(); 
     me.root = new TreeNode(); 

     me.root.left = new TreeNode(); 
     me.root.right = new TreeNode(); 

     me.root.left.left = new TreeNode(); 
     me.root.left.right = new TreeNode(); 
     me.root.left.left.right = new TreeNode(); 

     me.root.left.left.right.right = new TreeNode(); 

     System.out.println(me.maxDepth()); 

    } 

}