0

インオーダーおよびポストオーダー トラバーサルによる LCA は、簡単に実装でき、理解できました。

ただし、再帰的なボトムアップ アプローチがあります。

私はオンラインでコードを見ましたが、1行理解できませんでした:

コードは次のとおりです。

public Node lowestCommonAncestor(int val1, int val2,Node root){
    if(root == null){
        return null;
    }
    if(root.data == val1 || root.data == val2){
        return root;
    }

    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    if(left != null && right != null){
        return root;
    }
    return left != null ? left : right;
}

val1 と val2 は、LCA を見つける必要がある 2 つのノードの値です。

最後の行は私が立ち往生しているところです。

return left != null ? left : right;

誰かがこれを説明できますか？

ありがとうございました。

4

2 に答える 2

2

これは単純なアプローチの（一種の）きちんとした実装ですが、標準のボトムツートップではなくトップツーボトムで実装されています。lowestCommonAncestor(int val1, int val2,Node root)何が返されるかを分析してみましょう。

leftの左サブツリーにval1との少なくとも 1 つが見つかった場合、 は null にはなりません。同様に、との少なくとも 1 つがの右サブツリーにある場合に限り、 right は null ではありません。どうやら if ステートメントは、正確にとの 1 つが左のサブツリーにあり、正確にとの 1 つが右のサブツリーにある場合にのみ真になります。したがって、これはandの最下位の共通祖先に対してのみ発生します (必要に応じて絵を描いてください)。このノードでは、ルートが返されます。他のすべてのノードの場合、関数はval2rootval1val2rootif(left != null && right != null){val1val2val1val2val1val2lowestCommonAncestor両方が null の場合、どちらが null でないか、または null でないかに応じて、左または右のサブツリー内。

したがって、LCA より上のすべてのノードでは、正確に右と左の 1 つが null ではなく (サブツリーの 1 つにあるため)、それが LCA があるサブツリーのルートになりますval1。val2結果として、lowestCommonAncestorLCA より上のすべてのノードの呼び出しの戻り値は、LCA 自体になります。結果として、元のツリーのルートでの呼び出しは実際には LCA になります。

于 2015-10-06T10:24:21.517 に答える
1 
// Method to find lowest common ancestor.
public Node lowestCommonAncestor(int val1, int val2,Node root){

    // Base condition to terminate.
    if(root == null){
        return null;
    }

    // While traversing, if we found root itself equal to val1/val2.
    // Then, root should be the lowest common ancestor.
    if(root.data == val1 || root.data == val2){
        return root;
    }

    // If not, do post-order traversing. Means, left node, then right 
    // node, then root iteslf (current node.)
    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    // While traversing, if we reach to a state, when root itself has left and 
    // right both children, then, this is the lowest common ancestor of val1, 
    // and val2. return this root.
    if(left != null && right != null){
        return root;
    }

    // If, root has only one child either  left or right child, then start 
    // traversing into that child.
    // If, root has no child, in that case. Return null. Means this tree does    
    // not contain lowest common ancestor of val1, and val2.
    return left != null ? left : right;
}

コメントを入れてコード全体を説明しました。そのほうが理にかなっていると思います。通り抜けてください。それでも不明な点があれば、遠慮なく質問してください。

于 2015-10-06T10:35:52.547 に答える