再帰を使用してバイナリツリーで最も低い共通祖先

Question

私は、トップダウン再帰を使用してバイナリツリーの問題最小共通共通祖先（LCA）の問題を解決しようとしています。

私が使用しているアプローチである：

IDEA：他の所望のノードが反対のサブツリーであるいずれかのサブツリー内の所望のノードのうちの1つを有するノードを探します。

PSEUDOCODE 
1. If the value of root is equal to either of the desired node's value, 
    the root is the LCA. 
2. Search in the left subtree for either node. 
3. Search in the right subtree for either node. 
4. If neither of them contains any of the two nodes, 
    the nodes do not exist in the tree rooted at the root node. 
5. If each of them contains one node, 
    the root is the LCA. 
6. If either one of them contains a node, 
    return it to the root. 

また、これはStackOverflowの上related questionsの答えで推奨されているものです。
このコードは、ツリーのすべてのノードが一意の値であると仮定するとうまくいきます。つまり、このアプローチは重複の場合には破損しているようです

重複した値でも動作するようにコードを修正するにはどうすればいいですか？この方法で最適な解決策が得られない場合は、どのように私のアプローチを変更する必要がありますか？ここ

は、正確な実装である：例えば

class TreeNode(object): 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 

    def __repr__(self): 
     return 'TreeNode({}, {}, {})'.format(self.val, self.left, self.right) 

def lowestCommonAncestor(root, p, q): 
    """ 
    :type root: TreeNode 
    :type p: TreeNode 
    :type q: TreeNode 
    :rtype: TreeNode 
    """ 
    if root is None: 
     return None 

    if p.val == root.val or q.val == root.val: 
     return root 

    left_subtree = lowestCommonAncestor(root.left, p, q) 
    right_subtree = lowestCommonAncestor(root.right, p, q) 

    if left_subtree is None and right_subtree is None: 
     return None 

    if left_subtree is not None and right_subtree is not None: 
     return root 

    if left_subtree is None: 
     return right_subtree 
    else: 
     return left_subtree 

：

root = TreeNode(2) 
root.left = TreeNode(3) 
root.left.left = TreeNode(1) 
root.right = TreeNode(5) 
root.right.left = TreeNode(7) 
root.right.right = TreeNode(1) 
print(lowestCommonAncestor(root, TreeNode(1), TreeNode(7))) 

これは結果として、ツリーのルートを返します。 result = TreeNode（2）

疑いもなく、ルートは常に祖先です。
しかし、根よりも "下位の"共通祖先が存在します - TreeNode(5)。

Answer 1

問題があります： 1）なぜNode.valを確認していますか？あるノードと他のノードを直接比較するだけで済みます。それは同じ値を持つ複数のノードを持つツリーを持つときに問題を解決するはずです...それがあなたの唯一の問題であると仮定します。

2）なぜ、左のサブツリーが空でなく、右のサブツリーが空でない場合に、ルートを返すのですか？多くの場合、もちろん、それはrootを返します。これは一般に私たちが望む行動ではありません。

アルゴリズムを一から見直したいと思うかもしれません（いくつかの素晴らしいアイデアがありますが、いくつかの間違いを犯していることがわかりました。この問題はかなり単純/直接的なものであるため、 ）。

提案：この問題はツリー上の問題であり、検索/パスと関係しているため、ノードpからノードqまでのパスを見つける問題を考慮してください。ツリー内には、任意の2つのノードから正確に1つのパスが存在することがわかります（これは、ツリーが定義によって接続された非循環グラフであるという事実から単純に続きます）。

ベースケースに再帰した後、またはベースケースに再帰した後に訪問したノードをループに保存してから、いくつかの条件をテストするためのデータ構造を作成したい場合や、 （本質的にDFSのアプローチとBFSのアプローチ、BFSのアプローチでは明示的なメモ/メモリを使用しますが、DFSではスタックを使用して物事を覚えています）。

Answer 2

コードは、アイデアは、このようなものです。この

def lowestCommonAncestor(root, p, q): 
""" 
:type root: TreeNode 
:type p: TreeNode 
:type q: TreeNode 
:rtype: TreeNode 
""" 
flag=0 
if root is None: 
    return None 

if p.val == root.val or q.val == root.val: 
    flag=1 
    #return root 

left_subtree = lowestCommonAncestor(root.left, p, q) 
right_subtree = lowestCommonAncestor(root.right, p, q) 

if left_subtree is None and right_subtree is None: 
    if flag==0: 
     return None 
    else: 
     return root 

if left_subtree is not None and right_subtree is not None: 
    return root 

if left_subtree is None: 
    if flag==1: 
     if (right_subtree.value!=p && right_subtree.value!=q) || right_subtree.value==root.value: 
      return right_subtree 
     elif right_subtree.value!=root.value: 
      return root 
    else: 
     return right_subtree 
else: 
    if flag==1: 
     if (left_subtree.value!=p && left_subtree.value!=q) || left_subtree.value==root.value: 
      return left_subtree 
     elif left_subtree.value!=root.value: 
      return root 
    else: 
     return left_subtree 

Answer 3

次のようになります。私たちは、再帰的ルートの左右の部分木にpとqを検索します。左のサブツリーの結果がヌルならば、それはpを意味し、qはルートの左にないので、LCAがルートの右のサブツリーに存在しなければならないと安全に結論付けることができます。右サブツリーの結果がヌルの場合も同様の結論が成り立ちます。しかし、どちらもヌルでなければ、pとqはルートのいずれかの側を取ることを示します。したがって、根はLCAです。

class Solution { 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
     if (root == null) { 
      return root; 
     } 

     if (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; 
     } else if (left != null) { 
      return left; 
     } else { 
      return right; 
     } 
    } 
}