leetcode236：二叉树的最近公共祖先 #43

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   字节

   on May 17, 2020
2. sisterAn commented on May 17, 2020

   

   sisterAn

   on May 17, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解答：递归实现

   解题思路：

   如果树为空树或 p 、 q 中任一节点为根节点，那么 p 、 q 的最近公共节点为根节点

   如果不是，即二叉树不为空树，且 p 、 q 为非根节点，则递归遍历左右子树，获取左右子树的最近公共祖先，

   • 如果 p 、 q 节点在左右子树的最近公共祖先都存在，说明 p 、 q 节点分布在左右子树的根节点上，此时二叉树的最近公共祖先为 root
   • 若 p 、 q 节点在左子树最近公共祖先为空，那 p 、q 节点位于左子树上，最终二叉树的最近公共祖先为右子树上 p 、q 节点的最近公共祖先
   • 若 p 、 q 节点在右子树最近公共祖先为空，同左子树 p 、 q 节点的最近公共祖先为空一样的判定逻辑
   • 如果 p 、 q 节点在左右子树的最近公共祖先都为空，则返回 null

   代码实现：

   const lowestCommonAncestor = function(root, p, q) {
       if(root == null || root == p || root == q) return root
       const left = lowestCommonAncestor(root.left, p, q)
       const right = lowestCommonAncestor(root.right, p, q)
       if(left === null) return right
       if(right === null) return left
       return root
   };

   复杂度分析：

   时间复杂度：O(n)

   空间复杂度：O(n)

   leetcode
3. rocky-191 commented on May 18, 2020

   

   rocky-191

   on May 18, 2020

   Last edited by sisterAn

   More actions

   const lowestCommonAncestor=function(root,p,q){
   	if(root==null || root==p || root==q){
         return root
       }
       const left=lowestCommonAncestor(root.left,p,q);
       const right=lowestCommonAncestor(root.right,p,q);
       if(left==null) return right;
       if(right==null) return left;
       return root;
   }
4. plane-hjh commented on May 18, 2020

   

   plane-hjh

   on May 18, 2020

   More actions

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @param {TreeNode} p
    * @param {TreeNode} q
    * @return {TreeNode}
    */
   var lowestCommonAncestor = function(root, p, q) {
       if(root == null || root == p || root == q){
           return root;
       }
       let left = lowestCommonAncestor(root.left,p,q);
       let right = lowestCommonAncestor(root.right,p,q);
       if(left != null && right != null){
           return root;
       }
       return left != null ? left : right;
   };
5. luweiCN commented on May 18, 2020

   

   luweiCN

   on May 18, 2020

   More actions

   1. 从根节点递归往下找，找到一个节点，这个节点满足p和q分别在这个节点的左右子树上就是满足条件的
   2. 但是如果找到一个节点发现p和q同时在左子树或者右子树上，说明p和q一个是另一个的子节点，也就是说最近公共祖先是p和q自身中的一个，那么只要继续往下找，先找到谁就返回谁

   var lowestCommonAncestor = function (root, p, q) {
     function isInTree(root, node) {
       if (root === null) return false;
       if (root === node) return true;
       return isInTree(root.left, node) || isInTree(root.right, node);
     }
     let current = root;
     while (true) {
       if (current === p || current === q) return current;
       if (isInTree(current.left, p)) {
         if (isInTree(current.right, q)) {
           return current;
         } else {
           current = current.left;
         }
       } else {
         if (isInTree(current.left, q)) {
           return current;
         } else {
           current = current.right;
         }
       }
     }
   };
6. cutie6 commented on Nov 13, 2020

   

   cutie6

   on Nov 13, 2020

   More actions

   解答：递归实现

   解题思路：

   如果树为空树或 p 、 q 中任一节点为根节点，那么 p 、 q 的最近公共节点为根节点

   如果不是，即二叉树不为空树，且 p 、 q 为非根节点，则递归遍历左右子树，获取左右子树的最近公共祖先，

   • 如果 p 、 q 节点在左右子树的最近公共祖先都存在，说明 p 、 q 节点分布在左右子树的根节点上，此时二叉树的最近公共祖先为 root
   • 若 p 、 q 节点在左子树最近公共祖先为空，那 p 、q 节点位于左子树上，最终二叉树的最近公共祖先为右子树上 p 、q 节点的最近公共祖先
   • 若 p 、 q 节点在右子树最近公共祖先为空，同左子树 p 、 q 节点的最近公共祖先为空一样的判定逻辑
   • 如果 p 、 q 节点在左右子树的最近公共祖先都为空，则返回 null

   代码实现：

   const lowestCommonAncestor = function(root, p, q) {
       if(root == null || root == p || root == q) return root
       const left = lowestCommonAncestor(root.left, p, q)
       const right = lowestCommonAncestor(root.right, p, q)
       if(left === null) return right
       if(right === null) return left
       return root
   };

   复杂度分析：

   时间复杂度：O(n)

   空间复杂度：O(n)

   leetcode

   这思路是怎么想到的，有什么可迁移的方法套路嘛