This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

😄


  \color{red}{~}

Then do it! This column is all about the topic of binary trees, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. The content of binary tree is not much, but it is necessary for every programmer to understand the red black tree, B+ tree, LSM tree are very helpful and so on

Leveldb and Rocksdb implemented by WAL+ Lsm-tree

B + tree mysql

(HBASE) – LSM-Tree converts random write to sequential write, supports multiple layers compaction and lookup, and supports write amplification and read amplification

TokuDB –Fractal Tree

There’s more to discover.

  • Sequential traversal in a binary tree – iteration, recursion
  • Binary tree before sequential traversal – iteration, recursion
  • Binary tree after sequential traversal – iteration, recursion
  • Binary tree sequence traversal – iteration, recursion
  • Maximum depth of binary tree – iterative, recursive
  • Symmetric binary tree of binary tree – iteration, recursion
  • Binary tree path sum – iterative, recursive
  • Construct binary tree – iteration and recursion 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

class TreeNode {
    int val;          / / head node
    TreeNode left;    / / the left subtree
    TreeNode right;   / / right subtree

    TreeNode(intx) { val = x; }}// Test method
 public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        System.out.println("XXXX result =" + preorderTraversal(treeNode));
}        
Copy the code
  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

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Recursive exit
        if (root == null || root == p || root == q) {
            return root;
        }
        // Go to the left subtree of the node
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // Go to the right subtree of the node
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            // If there is no left subtree, it is on the right subtree
            return right;
        } else if (right == null) {
            // If the right subtree does not exist, it is on the left subtree
            return left;
        }
        // Left and right, indicating that the node is the nearest common ancestor
        return root;
    }



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! ❤ ️ ❤ ️ ❤ ️ ❤ ️