236. The binary tree in recent common ancestor

打卡!!!每日一题

Today I bring you a tree type topic,Is also a more classic depth-first traversal

题目描述：236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先.

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）.”

题目示例：

The topics can be roughly divided into the following situations：

• If any one of the two nodes are the root node,Then we can directly return to the root node
• If two nodes are on both sides of the tree,then their nearest common ancestor can only be the root node
• The hardest case is when two nodes are on the same side of the tree

对于p或q是根节点的情况,我们只需判断p或qIs it equal to the root node?

if (p.val == root.val || q.val == root.val) {
    
            return root;
        }

Determine if it is on both sides of the tree,We only need to divide the left and right subtrees

        int rootIndex = allNodeVal.indexOf(root.val);
        int pIndex = allNodeVal.indexOf(p.val);
        int qIndex = allNodeVal.indexOf(q.val);
        /**2.two nodes on either side of the tree**/
        if (pIndex < rootIndex && qIndex > rootIndex || pIndex > rootIndex && qIndex < rootIndex) {
    
            return root;
        }

The two nodes on the same side,我们需要用一个HashTable stores all parent nodes of each node,然后获取p,qlist of parent nodes,Because we need the deepest parent node ,So we can consider using inorder traversal of the binary tree,This layer of the deepest node will be in front of the list

    public void dfs(TreeNode root) {
    
        if (root == null) return;
        if (root.left != null) {
    
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
    
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

完整代码如下：

package com.exercise.leetecode.problem.剑指offer.前中后序遍历;

import com.exercise.leetecode.common.TreeNode;

import java.util.*;

public class 二叉树的最近公共祖先_236 {
    
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    List<Integer> allNodeVal = new ArrayList<>();
    TreeNode r;//存放根节点

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        /**1.Indicate that one of the nodes is the root node**/
        if (p.val == root.val || q.val == root.val) {
    
            return root;
        }
        //Determine if two nodes are on the same side
        r = root;
        dfs_in(root);
        root = r;
        boolean sig_p = false, sig_q = false;
        int rootIndex = allNodeVal.indexOf(root.val);
        int pIndex = allNodeVal.indexOf(p.val);
        int qIndex = allNodeVal.indexOf(q.val);
        /**2.two nodes on either side of the tree**/
        if (pIndex < rootIndex && qIndex > rootIndex || pIndex > rootIndex && qIndex < rootIndex) {
    
            return root;
        }
        dfs(root);
        List<TreeNode> pParent = new ArrayList<>();
        pParent.add(p);
        while (p != null) {
    
            p = parent.get(p.val);
            pParent.add(p);
        }
        List<Integer> qParent = new ArrayList<>();
        qParent.add(q.val);
        while (q != null) {
    
            q = parent.get(q.val);
            if (q != null) {
    
                qParent.add(q.val);
            }

        }
        for (TreeNode t : pParent) {
    
            if (qParent.contains(t.val)) {
    
                return t;
            }
        }
        return null;
    }

    public void dfs_in(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        dfs_in(root.left);
        allNodeVal.add(root.val);
        dfs_in(root.right);
    }

    public void dfs(TreeNode root) {
    
        if (root == null) return;
        if (root.left != null) {
    
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
    
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}