12

バイナリ ツリーの最大深度を見つけるための再帰的メカニズムは非常に簡単ですが、この再帰を避けたい大きなツリーがあるため、再帰なしで効率的に行うにはどうすればよいでしょうか。

//Recursive mechanism which I want to replace with non-recursive
private static int maxDepth(Node node) {
if (node == null) return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right)); 
}

PS: Java で回答を探しています。

4

7 に答える 7

13

このバリアントは 2 つのスタックを使用します。1 つは追加ノードを探索するためのもの ( wq) で、もう 1 つは常にルートからの現在のパスを含むもの ( path) です。両方のスタックの一番上に同じノードが表示されている場合は、その下のすべてを調べてポップできることを意味します。これは、ツリーの深さも更新する時です。ランダムまたはバランスの取れたツリーでは、追加のスペースは O(log n) である必要があります。もちろん、最悪の場合は O(n) です。

static int maxDepth (Node r) {
    int depth = 0;
    Stack<Node> wq = new Stack<>();
    Stack<Node> path = new Stack<>();

    wq.push (r);
    while (!wq.empty()) {
        r = wq.peek();
        if (!path.empty() && r == path.peek()) {
            if (path.size() > depth)
                depth = path.size();
            path.pop();
            wq.pop();
        } else {
            path.push(r);
            if (r.right != null)
                wq.push(r.right);
            if (r.left != null)
                wq.push(r.left);
        }
    }

    return depth;
}

(恥知らずなプラグイン: 数週間前に、非再帰的なトラバーサルにデュアル スタックを使用するというアイデアがありました。ここで C++ コードを確認してください http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree- traversal.htmlを発明したのは私が最初だと主張しているわけではありません :)

于 2013-11-11T19:43:12.763 に答える
2

再帰を伴わず、スペースの複雑さを増すことなく、最大および最小の深さを見つけるための次のロジックを作成しました。

// Find the maximum depth in the tree without using recursion
private static int maxDepthNoRecursion(TreeNode root) {
    return Math.max(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
}

// Find the minimum depth in the tree without using recursion
private static int minDepthNoRecursion(TreeNode root) {
    return Math.min(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
}

private static int maxDepthNoRecursion(TreeNode root, boolean left) {
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    int depth = 0;
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (left && node.left != null) stack.add(node.left);
        // Add the right node only if the left node is empty to find max depth
        if (left && node.left == null && node.right != null) stack.add(node.right); 
        if (!left && node.right != null) stack.add(node.right);
        // Add the left node only if the right node is empty to find max depth
        if (!left && node.right == null && node.left != null) stack.add(node.left);
        depth++;
    }
    return depth;
}
于 2013-11-10T06:01:52.427 に答える
2

あなたが説明した再帰的なアプローチは、本質的にバイナリツリー上の DFS です。必要に応じて、ノードの明示的なスタックを格納し、検出された最大深度を追跡することで、これを繰り返し実装できます。

お役に立てれば！

于 2013-11-10T04:51:54.547 に答える
1

もう 1 つの方法はLevel order traversal、木の高さが木のレベルの数に等しい を使用することです。(木の最小の高さを計算するためにのみ使用できます。)

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    LinkedList<TreeNode> arr = new LinkedList<TreeNode>(); // queue for current level
    LinkedList<TreeNode> tmp = new LinkedList<TreeNode>(); // queue for next level
    arr.add(root);
    int res = 0; // result
    TreeNode node; // tmp node 
    while (true) {
        while (!arr.isEmpty()) {
            node = arr.poll();
            if (node.left != null) tmp.add(node.left);
            if (node.right != null) tmp.add(node.right);
        }
        res++;
        if (tmp.isEmpty()) break;
        arr = tmp;
        tmp = new LinkedList<TreeNode>();
    }
    return res;
}
于 2015-10-11T17:10:32.363 に答える
0

配列を使用してノードのレイヤーを格納し、毎回新しいレイヤーを見つけます。深さプラスワン。 

public int maxDepth2(TreeNode root){
        if(root == null){
            return 0;
        }

        int depth = 0;

        ArrayList<TreeNode> oneLayer = new ArrayList<TreeNode>();
        oneLayer.add(root);

        while(!oneLayer.isEmpty()){
            ArrayList<TreeNode> newLayer = new ArrayList<TreeNode>();
            for(TreeNode node:oneLayer){
                if(node.right!=null){
                    newLayer.add(node.right);
                }
                if(node.left!=null){
                    newLayer.add(node.left);
                }
            }
            oneLayer = newLayer;
            depth++;
        }

        return depth;
    }
于 2016-01-04T07:18:47.843 に答える
0

各ノードで左右の値を維持できれば、それは可能です。

http://leetcode.com/2010/04/maximum-height-of-binary-tree.html .

重複の可能性: バイナリ ツリー ノードの深さを非再帰的に取得する

于 2013-11-10T04:36:18.477 に答える