Leetcode brush question: binary tree 24 (the nearest common ancestor of binary tree)

236. The nearest common ancestor of a binary tree

Force button topic link

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

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

for example , Given the following binary tree : root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:
Input : root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output : 3
explain : node 5 And nodes 1 The most recent public ancestor of is the node 3.

Example 2:
Input : root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output : 5
explain : node 5 And nodes 4 The most recent public ancestor of is the node 5. Because by definition, the nearest common ancestor node can be the node itself .

explain :

• The values of all nodes are unique .
• p、q For different nodes and all exist in a given binary tree .

At first glance, this problem is not difficult , Is to find the path of these two nodes , Then compare the values on the path , Find the last equal node .
Recursive traversal , If both nodes are found , Stop recursion . Pay attention to whether it is a single branch node when recursing , The leaf node cannot be null As a condition of termination , Otherwise, delete the path taken twice , The node is missing , The path jumps to the node . To judge , Delete the repeated paths one by one .
Finally, when traversing , I've had this card for a long time , Maybe I'm confused when I brush the questions , similar 3 5 and 3 5 4 2 such , Find the last common element , I did it for half an hour , speechless , Using pointer method .
Can't do , Stop. Stop , Take a walk .

package com.programmercarl.tree;

import com.programmercarl.util.GenerateTreeNode;

import java.util.*;

/** * @ClassName LowestCommonAncestor * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 10:12 * @Version 1.0 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ * 236.  The nearest common ancestor of a binary tree  **/
public class LowestCommonAncestor {
    
    /** *  Given a binary tree ,  Find the nearest common ancestor of the two specified nodes in the tree . *  In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree  T  Two nodes of  p、q, The nearest common ancestor is represented as a node  x, *  Satisfy  x  yes  p、q  Our ancestors and  x  As deep as possible （ A node can also be its own ancestor ）.” *  source ： Power button （LeetCode） *  link ：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree *  Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source . * * @param root * @param p * @param q * @return */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        /** *  have a lucid brain ： *  Find the path of two nodes  *  Path value comparison , When the values are not equal , Return the previous path value  */
        this.p = p;
        this.q = q;
        traversal(root);

        int size = Math.min(pPathNode.size(), qPathNode.size());
        // Point to common elements 
        TreeNode result = pPathNode.get(0);
        for (int i = 1; i < size; i++) {
    
            if (pPathNode.get(i).val == qPathNode.get(i).val) {
    
                result = pPathNode.get(i);
            }
        }
// pPathNode.stream().forEach((item) -> System.out.print(item.val));
// System.out.println();
// qPathNode.stream().forEach((item) -> System.out.print(item.val));
// System.out.println();
        return result;
    }

    boolean isFindPandQ = false;
    TreeNode p;
    TreeNode q;
    List<TreeNode> pPathNode = new ArrayList<TreeNode>();
    List<TreeNode> qPathNode = new ArrayList<TreeNode>();
    List<TreeNode> curPathNode = new ArrayList();

    public void traversal(TreeNode root) {
    
        if (isFindPandQ) {
    
            // The discovery is complete , Stop recursion 
            return;
        }


        curPathNode.add(root);

        if (root.val == p.val) {
    
            pPathNode = new ArrayList<>(curPathNode);
            // Stop recursion when both are found 
            isFindPandQ = pPathNode.size() > 0 && qPathNode.size() > 0;
        }

        if (root.val == q.val) {
    
            qPathNode = new ArrayList<>(curPathNode);
            // Stop recursion when both are found 
            isFindPandQ = pPathNode.size() > 0 && qPathNode.size() > 0;
        }
        // Discuss the two situations separately , Prevent the leaf node from deleting the last position twice 
        if (root.left != null) {
    
            traversal(root.left);
        }
        if (root.right != null) {
    
            traversal(root.right);
        }
        curPathNode.remove(curPathNode.size() - 1);
    }

    public static void main(String[] args) {
    
        System.out.println(new LowestCommonAncestor().lowestCommonAncestor(GenerateTreeNode.generateTreeNode("[3,5,1,6,2,0,8,null,null,7,4]"), new TreeNode(5), new TreeNode(4)).val);
        System.out.println(new LowestCommonAncestor().lowestCommonAncestor(GenerateTreeNode.generateTreeNode("[3,5,1,6,2,0,8,null,null,7,4]"), new TreeNode(5), new TreeNode(1)).val);
    }
}