[LeetCode]236. Lowest Common Ancestor of a Binary Tree
题目描述
思路
深搜 对于传入的节点，首先判断根节点是否为空，若为空直接返回 之后判断传入的节点是否有一个是根节点，若有，直接返回根节点 之后分别查看左右子树是否有目标节点，若都有，则返回根节点 若都在左子树或者都在右子树，则再去对应的子树查找
代码
#include <iostream>
using namespace std;
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 ==
NULL || root == p || root == q)
return root;
TreeNode*
left = lowestCommonAncestor(root->
left, p, q);
TreeNode*
right = lowestCommonAncestor(root->
right, p, q);
if (
left &&
right)
return root;
else
return
left ?
left :
right;
}
};
