首页 > 其他 > 详细

236. Lowest Common Ancestor of a Binary Tree

时间:2020-11-29 23:02:39      阅读:26      评论:0      收藏:0      [点我收藏+]

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

技术分享图片
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

技术分享图片
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.
 
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //还是递归解法:在左子树中递归找p或q,如果找到一个就返回;在右子树中找p或q如果找到一个就返回那个节点,没找到就返回NULL。
    //如果左子树中找到一个,右子树中也找到一个,那么这两个子树的根节点就是结果。
    //如果左子树中没有找到,那么返回空,说明两个节点都在右子树。否则都在左子树。
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL;
        if(root==p||root==q)  return root;
        TreeNode* ltree=lowestCommonAncestor(root->left,p,q);
        TreeNode* rtree=lowestCommonAncestor(root->right,p,q);
        //分别在左右子树中找到
        if(ltree&&rtree)  return root;
        //右三种情况在此处返回
        //在左右某个子树中没找到任一个p或q
        //第一次在当前节点左子树或者右子树中找到p或q
        //当前节点的左右子树找到p‘q
        return  ltree?ltree:rtree;
    }
};

 

236. Lowest Common Ancestor of a Binary Tree

原文:https://www.cnblogs.com/wsw-seu/p/14057078.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!