236.-lowest-common-ancestor-of-a-binary-tree.md

236. Lowest Common Ancestor of a Binary Tree

{% tabs %} {% tab title="Go" %}

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  
     // 原function 就是return node的
     if root == nil{
         return root
     }
     if root == p || root == q {
        return root
    }
     // 剩下就是root 有 且不为孩子
     left := lowestCommonAncestor(root.Left, p, q)
     if left != nil && left != q && left != p{
         return left
     }
     right := lowestCommonAncestor(root.Right, p, q)
     
     if left != nil && right != nil{
         return root
     }else if left != nil && right == nil{
         return left
     }
     return right
     
}

{% endtab %}

{% tab title="" %}

 /**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil || p == nil || q == nil {
         return nil
     }
     pathQ := getPath(root,q)
     pathP := getPath(root,p)
     var ans *TreeNode
     
     for i := 0 ; i < len(pathQ) && i < len(pathP);i++ {
         if pathQ[i].Val == pathP[i].Val {
             ans = pathQ[i] 
         } else {
            break
         }
     }
     return ans
          
 }
func getPath(root, n *TreeNode) []*TreeNode {
    s := make([]*TreeNode,0)
    var lastVisited *TreeNode
    for s != nil || root != nil {
        if root != nil {
            s = append(s,root)
            root = root.Left
        } else {
            node := s[len(s)-1]
            if node.Right != nil && lastVisited != node.Right {
                root = node.Right
            } else {
                if node == n {
                    return s
                }
                lastVisited = s[len(s)-1]
                s = s[:len(s)-1]
                root = nil
            }
        }
        
    }
    return s
}

{% endtab %}

{% tab title="" %}

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */

// 熟悉指针操作.从OJ来看性能无差异
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil || p == nil || q == nil {
         return nil
     }
     pathQ := getPath(root,q)
     pathP := getPath(root,p)
     var ans *TreeNode
     
     for i := 0 ; i < len(*pathQ) && i < len(*pathP);i++ {
         if (*pathQ)[i].Val == (*pathP)[i].Val {
             ans = (*pathQ)[i] 
         } else {
            break
         }
     }
     return ans
          
 }
func getPath(root, n *TreeNode) *[]*TreeNode {
    s := make([]*TreeNode,0)
    var lastVisited *TreeNode
    for s != nil || root != nil {
        if root != nil {
            s = append(s,root)
            root = root.Left
        } else {
            node := s[len(s)-1]
            if node.Right != nil && lastVisited != node.Right {
                root = node.Right
            } else {
                if node == n {
                    return &s
                }
                lastVisited = s[len(s)-1]
                s = s[:len(s)-1]
                root = nil
            }
        }
        
    }
    return &s
}

{% endtab %}

{% tab title="Python" %}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.c = 0
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        ### iterative 
        
        # DFS [1,2,3,q] [1,2,3,p] ,所以3 就是 lowest 
        
        if not root:
            return root
        
        if p == root or q == root:
            self.c += 1
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        print(left)
        if left and left != p and left !=q :
            return left
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right and self.c == 2:
            return root
        return left if left else right

                    
                
            
        

{% endtab %} {% endtabs %}