【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

  • Construct binary tree | Go theme month by traversing sequence from middle order to back order

Leecode 236. The most recent common ancestor of binary trees

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

 

Example 1:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 1

Output: 3

The most recent common ancestor of nodes 5 and 1 is node 3.

Example 2:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4

Output: 5

The most recent common ancestor of nodes 5 and 4 is node 5. Because by definition the nearest common ancestor node can be the node itself.

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

Let’s take this tree as an example

Key points:

  1. Recursive export

  2. Look in the left subtree of that node

  3. Go to the right subtree of that node

  4. It indicates that the node is the most recent common ancestor

  5. Not on the left subtree, which means it’s on the right subtree

  6. If not on the right subtree, it’s on the left subtree

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {  / / 1.
        return nil  
    }
    if root.Val == p.Val || root.Val == q.Val {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)  / / 2.
    right := lowestCommonAncestor(root.Right, p, q)  / / 3.
    ifleft ! =nil&& right ! =nil {
        return root   / / 4.
    }
    if left == nil {   / / 5.
        return right
    }
    return left  / / 5.
}



Copy the code

The iterative version

The core and recursion are pretty much the same.

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    parent := map[int]*TreeNode{}
    visited := map[int]bool{}

    var dfs func(*TreeNode)
    dfs = func(r *TreeNode) {
        if r == nil {
            return
        }
        ifr.Left ! = nil { parent[r.Left.Val] =r
            dfs(r.Left)
        }
        if r.Right != nil {
            parent[r.Right.Val] = r
            dfs(r.Right)}}dfs(root)

    for p != nil {
        visited[p.Val] = true
        p = parent[p.Val]
    }
    forq ! = nil {if visited[q.Val] {
            return q
        }
        q = parent[q.Val]
    }

    return nil
}



Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️