二叉树的最近公共祖先

[编程题]二叉树的最近公共祖先

热度指数：383 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

例：图中给定树 {3,5,1,6,2,0,8,#,#,7,4} 中，节点6、节点4的最近公共祖先为5。

示例1

输入

{3,5,1,6,2,0,8,#,#,7,4},{6},{4}

输出

{5,6,2,#,#,7,4}

备注:

注意：使用root.val == p.val、root.val == q.val判断root==p、root==q

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

张先生－您好

class Solution:
    def nearestCommonAncestor(self , root , p , q ):
        # write code here
        if not root&nbs***bsp;root.val == q.val&nbs***bsp;root.val == p.val:
            return root
        
        left = self.nearestCommonAncestor(root.left, p, q)
        right = self.nearestCommonAncestor(root.right, p, q)
        if not left: return right
        if not right: return left
        
        return root

发表于 2021-08-31 09:29:58 回复(0)

BugNotFoundException

简单题

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
  /**
   * 
   * @param root TreeNode类 
   * @param p TreeNode类 
   * @param q TreeNode类 
   * @return TreeNode类
  */
  public TreeNode nearestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
      return null;
    }
    if (root.val == p.val || root.val == q.val) {
      return root;
    }
    TreeNode leftAns = nearestCommonAncestor(root.left, p, q), 
    rightAns = nearestCommonAncestor(root.right, p, q);
    if (leftAns != null && rightAns != null) {
      return root;
    }
    return leftAns != null ? leftAns : rightAns;
  }
}

发表于 2022-03-30 15:49:41 回复(0)

挚爱麦香鱼

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return TreeNode类
     */
    public TreeNode nearestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) {
        // write code here
        return helper(root, p, q);
    }
    
    public TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root.val == p.val || root.val == q.val)
            return root;
        TreeNode left = helper(root.left, p, q), right = helper(root.right, p, q);
        if (left == null && right == null)
            return null;
        else if (left != null && right != null)
            return root;
        else
            return left == null ? right : left;
    }
}

发表于 2021-08-31 13:59:58 回复(0)