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:
[2, 105]
.-109 <= Node.val <= 109
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