2..LeetCode 字节跳动二叉树两节点最近的公共祖先节点

Love The Way You Lie 2023-06-06 03:35 15阅读 0赞

## 题目 ##

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

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

## 自己的答案 ##

public class TreeNode {
         int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }
     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //1.p与q中有一个是根节点
            if (root.equals(p) || root.equals(q)){
                return root;
            }
            //2.p 父节点集合  ,q 父节点集合,然后 比对
            final List<TreeNode> parentsTreeNodes = getParentsTreeNodes(root, p);
    
            final List<TreeNode> parentsTreeNodes1 = getParentsTreeNodes(root, q);
    
            for (TreeNode parentsTreeNode : parentsTreeNodes) {
                if (parentsTreeNodes1.contains(parentsTreeNode)){
                    return parentsTreeNode;
                }
            }
            return null;
        }
    
        List<TreeNode> getParentsTreeNodes(TreeNode root,TreeNode p){
            List<TreeNode> treeNodes=new ArrayList<>();
            TreeNode parentTreeNode = getParentTreeNode(root, p);
            treeNodes.add(p);
            while (parentTreeNode!=null){
                treeNodes.add(parentTreeNode);
                parentTreeNode=getParentTreeNode(root,parentTreeNode);
            }
            return treeNodes;
        }
    
    
       TreeNode getParentTreeNode(TreeNode node,TreeNode p){
            if (node==null){
                return null;
            }
              //root的节点是否为p的父节点
           final boolean b = checkP(node, p);
           if (b){
               return node;
           }else {
               TreeNode left=node.left;
               final boolean b1 = checkP(left, p);
               if (b1){
                   return  left;
               }else {
                  TreeNode right=node.right;
                   final boolean b2 = checkP(right, p);
                   if (b2){
                       return right;
                   }else {
                       final TreeNode parentTreeNode = getParentTreeNode(left, p);
                       if (parentTreeNode==null){
                           final TreeNode parentTreeNode1 = getParentTreeNode(right, p);
                           if (parentTreeNode1==null){
                               return null;
                           }else {
                               return parentTreeNode1;
                           }
                       }else {
                           return parentTreeNode;
                       }
                   }
               }
           }
    
       }
    
    
        boolean checkP(TreeNode node,TreeNode p){
            if (node!=null){
                if ((node.left!=null && node.left.val==p.val)||(node.right!=null && node.right.val==p.val)){
                    return  true;
                }else {
                    return  false;
                }
            }else {
                return false;
            }
        }

## 官方答案 ##

class Solution {
    
        private TreeNode ans;
    
        public Solution() {
            // Variable to store LCA node.
            this.ans = null;
        }
    
        private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
    
            // If reached the end of a branch, return false.
            if (currentNode == null) {
                return false;
            }
    
            // Left Recursion. If left recursion returns true, set left = 1 else 0
            int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
    
            // Right Recursion
            int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
    
            // If the current node is one of p or q
            int mid = (currentNode == p || currentNode == q) ? 1 : 0;
    
    
            // If any two of the flags left, right or mid become True
            if (mid + left + right >= 2) {
                this.ans = currentNode;
            }
    
            // Return true if any one of the three bool values is True.
            return (mid + left + right > 0);
        }
    
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // Traverse the tree
            this.recurseTree(root, p, q);
            return this.ans;
        }
    }

## 解析 ##

自己的结题思路:  
找p和q的祖先集合,按顺序(离p或q越近添加的越早),遍历这两个集合,因为遍历的时候是有顺序的,所以只要找到第一个公共的元素,则就是该节点(最近的祖先),需要注意的是 :别忘了遍历之前先查看自己是否在两个集合中,或者添加祖先之前先将自己添加进去;

官方答案:  
方法一：递归

这种方法非常直观。先深度遍历改树。当你遇到节点 p 或 q 时，返回一些布尔标记。该标志有助于确定是否在任何路径中找到了所需的节点。最不常见的祖先将是两个子树递归都返回真标志的节点。它也可以是一个节点，它本身是p或q中的一个，对于这个节点,子树递归返回一个真标志。

让我们看看基于这个想法的形式算法。

算法：

从根节点开始遍历树。
    如果当前节点本身是 p 或 q 中的一个，我们会将变量 mid 标记为 true，并继续搜索左右分支中的另一个节点。
    如果左分支或右分支中的任何一个返回 true，则表示在下面找到了两个节点中的一个。
    如果在遍历的任何点上，左、右或中三个标志中的任意两个变为 true，这意味着我们找到了节点 p 和 q 的最近公共祖先。

以下是递归中遵循的节点序列：

1 --> 2 --> 4 --> 8
    回溯 8 --> 4
    4 --> 9 (找到一个节点，返回true)
    回溯 9 --> 4 --> 2
    2 --> 5 --> 10
    回溯 10 --> 5
    5 --> 11 (找到另一个节点，返回true)
    回溯 --> 5 --> 2
    
    在2节点这里我们有左边=true，右边=true，因此 2 节点是它们的最近公共祖先

## 总结 ##

实际上,我与官方的递归思路是一样的只不过判定条件不同,那么为什么 官方的解析可以简单的判定,主要是自己对递归的理解还不够彻底,两条路的递归就有点懵逼了…  
递归中是带有回溯的,所以这点需要理解清楚,这个回溯并不是与递归分离的,并不是递归的运算中的一部分,只不过是我们在递归中更好的理解整个过程,所虚拟的步骤,其实是不存在的.回溯步骤之后,才是代码执行的递归过程