BSTの深さの計算方法を変更する

Question

パラメータを指定せずにBSTを宣言する場合、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()が現在のノードになります。

レイヤーごとにツリーをトラバースする場合、必要な2番目の情報は、次にどのノードにアクセスするかです。そのために、2番目のスタックを使用します（関数の内部状態を表します）。 2番目のスタックには、次のステップ（LEFT、RIGHT、DOWN）が格納されます。

これは複雑に見えますが、手作業で行う必要があります。これはプログラミング言語の関数スタックに隠されています。 Stack.popは関数の戻り値に対応します。 Stack.pushは、次の反復のためのパラメータを準備します。

私たちは、以下のプログラムで終わる：しかし、パラメータを持たない唯一のMAXDEPTH方法と、

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()); 

    } 

}