【LeetCode】236. Nearest common ancestor of binary tree

• Ideas
  The idea is to find the nearest common ancestor of the binary tree from the bottom up , So I thought of using After the sequence traversal Recursive method of . Then the difficulty is how to record the nearest common ancestor ？ To judge the ancestors , You must judge the value of child nodes from the root node , How else do you know who is its ancestor , So if it matches q or p, One of them records the current point （ Update ancestor , The method adopted is to modify the corresponding p or q Is the ancestor value ）, Then use the current point to match another , Two simultaneous matches are common ancestors .
  Wrote a version of the code , There is a problem , Refer to the explanation of the question
  Didn't figure out what to return , That is, there is no definite recursive trilogy
  Recursive parameters and return values ： If the return value is empty, it means that... Is not found , If it is not empty, it means that p or q;
  The termination condition of recursion ： If you find it node p perhaps q, Or an empty node , Just go back to ;
  Recursive single-layer logic ： The hardest part is to understand how to get the return value , Traversing a tree is not the same as traversing an edge - connected return value .
  

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    
    //  Termination conditions 
    if root == p || root == q || root == nil {
    
        return root
    }
    //  Left 
    left := lowestCommonAncestor(root.Left, p, q)
    //  Right 
    right := lowestCommonAncestor(root.Right, p, q)
    //  in 
    // 1. left empty ,right Not empty , shows right eureka , return 
    if left == nil && right != nil {
    
        return right
    }
    // 2. left Not empty ,right empty , shows left eureka , return 
    if left != nil && right == nil {
    
        return left
    }
    // 3.  All is empty 
    if left == nil && right == nil {
    
        return nil
    }
    // 4.  If they are not empty, they are all found , Then the present is the nearest common ancestor 
    return root
}

• summary
  Take this opportunity to summarize when recursive functions return values , When not .（ Reference code random notes ）