LeetCode-Lowest Common Ancestor of a Binary Tree

这道题在一个面试的时候没有通过,当时没有想到两个要找的元素会连成一条线,所以,就gg了。

现在想来,这道题其实挺简单的,元素也只用遍历一次。

首先,要坚信输入的p和q是存在于root为根节点的二叉树中的。返回的时候就返回最有可能成为父节点的那个元素就可以了。首先,如果遍历到有元素等于p或者q,那么就说明根节点可能是他们(就是我没想到的那种情况),不管如何,直接返回,因为如果根节点不是它们,那么另一个要找的节点肯定在另外的递归中可以遇到,如果是他们,那就对了,先被返回的肯定是层级更高的,也就是另一个节点的父节点。

如果不是p或者q的话,那么就需要通过递归来找p和q是在该节点的左子树还是右子树中了,如果左右子树都能找到该节点,那么就说明这个节点就是要找的节点,直接返回就行了,注意在这里是递归搜索,所以一定是在搜索了它所有的子节点以后才去计算的结果。

最后,如果搜索的时候不是左右子树都有返回值的话,那就说明可能有一边有,也可能两边都没有,有一边有的话,这个问题就可以归约到第二行代码的问题中,直接把找到的那个节点返回就可以了,如果没找到的话,就返回空。

最后写下来,其实代码可以非常简洁,但是我面试的时候太蠢了,所以还是挂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr) return nullptr;
if(root==p || root==q) return root;
TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
if(left!=nullptr && right!=nullptr) return root;
if(left!=nullptr) return left;
else return right;
}
};