5

私は次の実装に遭遇し、しばらく時間を費やしましたが、それでもアイデアを理解できません。誰かが行ごとにそれが何をしているのか説明してもらえますか? ノードが祖先であると判断できる時点がわかりません。

ありがとうございました

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}
4

4 に答える 4

3

ツリー ブランチ内の数値の存在をマークする基本的な考え方は、数値FOUNDには非 nullポインターを使用し、 NOTFOUNDにはnullポインターを使用することです。

p数値 (またはq) が見つかった場合、または が である場合、rootコールスタックは巻き戻されますnull。後で、検索された番号が存在しないことを明確に示します。

次の 4 つのシナリオが考えられます。

1.) 両方とも 1 つの親の下にある。

                      root
                      /  \ 
            Leftsubtree  Rightsubtree
                p/q        q/p

この場合、以下のコードでは、これが満たされる瞬間が来るでしょう。if(left != null && right != null) return root;

2.) 片方の親がもう一方の親。

      q/p                     p/q
      /            OR          \ 
Leftsubtree                 Rightsubtree
  p/q                           q/p

この場合、これは満たされますif(root == null || root == p || root == q) return root;

3.) どちらもツリーに存在しません。この状態は検出されません。ケース 2 に示すように、関数は、それ以上トラバースしてその下のツリーで対応する関数を探すことなく、すぐに戻ります。

4.) それらのいずれもツリーに存在しません。

最初の行if(root == null ... return ;は、存在しない子ごとに実行されます。数値が見つからないため、最終結果はnull返されます。

行ごとのコードの説明。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q)  return root;

    /* (root == null)  This proves that root is not in the branch of tree of our interest. Returning null would means NOTFOUND.*/
    /* (root == p || root == q) either p or q or both are found. Returning non-null root would means FOUND. */

    /*Check for presence in leftsubtree */
    TreeNode left = lowestCommonAncestor(root.left, p, q);

    /*Check for presence in rightsubtree */
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    /*            root
                  /  \ 
        leftsubtree  Rightsubtree
            p/q        q/p

    */
    if(left != null && right != null)   return root; //both the numbers are found inside tree under root 

    // left or right subtree OR both don't have p or q. Return the overall find result under root.
    return left != null ? left : right;
}
于 2016-11-21T07:59:23.560 に答える
1 
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // root == null (no root no LCA)
    // root == p || root == q (if either p or q is the root then root is LCA)
    if(root == null || root == p || root == q)  return root;
    //get the LCA of p and q in left sub tree
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    //get the LCA of p and q in right sub tree
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // if one of p or q is in left subtree and another is in the right subtree, 
    //then the root is the LCA
    if(left != null && right != null)   return root;
    // if left is not null, left is LCA, else right is LCA 
    return left != null ? left : right;
}
于 2016-11-21T05:18:09.160 に答える
0 
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root->val == p->val || root->val == q->val ||
        (p->val < root->val && root->val < q->val) ||
        (q->val < root->val && root->val < p->val)) {
        return root;
        }
    else if (root->val < p->val) return lowestCommonAncestor(root-> right, p, q);
    else return lowestCommonAncestor(root->left, p, q);

これがC++での私の答えですが、「->」を「。」に切り替える限り、非常に似ているはずです。構文。これは、現在の葉とその左右の子をチェックする再帰関数であり、最初の if ステートメントの条件が true になると、最も低い共通の祖先を識別したことを意味します。価値。

例: ルートとして 2 を指定し、その子 (それぞれ左と右) として 1 と 4 を指定すると、1 はルートよりも低くなりますが、4 はそうではないため、2 が最小公分母です。IT は最初の実行で停止します。

自分で二分木を描いて、各ステップをテストすると、より理にかなっているでしょう。

于 2016-11-21T07:44:00.710 に答える
0 
if(root == null || root == p || root == q)  return root;

currentroot nodeがnullの場合、現在の sub_tree には p と q が存在しcommon ancestorないため、戻りますnull root==null

およびpまたはqが等しい場合root。私はp=rootと仮定し、ここでqに関しては、それは p または p のどちらかですが、どちらの offspring場合でもpのnot offspringsub_treeをたどる必要はありません。前者の場合pがqの祖先である場合はppを返すだけです==root 、それ以外の場合はpを直接返します。この場合pはありませんが、エラーは発生しません。ステートメント については後で説明します。ancestor of q

if(left != null && right != null) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);


1. p と q はすべてroot.leftoffspringのものです
2. p と q はすべてoffspringroot.right のものです
3.これら 2 つのノードの 1 つはoffspringroot.left のもので、もう1 つはoffspringroot.rightのものです

これらの 2 つrecursive statementはcommon ancestor、p と q ( 1,2 の場合) を検索するために使用されます。そうでない場合は、 pとq ( 3 の場合)を検索するために使用されます。

if(left != null && right != null)   return root;

このステートメントは 3 の処理に使用されcorresponding result、pと q は root に存在するため、rootleft_subtree and right_suntreeも存在します。ancestor 

 return left != null ? left : right;

このステートメントは、 1,2、 p、およびqcorresponding resultの処理に使用され、左または右に同じ sub_tree が存在します。

于 2016-11-21T05:54:44.590 に答える