该算法的 运行 时间复杂度是多少？您如何对其进行分析？
What is the running time complexity of this algorithm? And HOW do you do the analysis for it?
-- 下面的 lowestCommonAncestor 函数在二叉树中找到两个节点 p 和 q 的最低公共祖先（假设两个节点都存在并且所有节点值都是独一无二）。
class Solution {
public:
bool inBranch(TreeNode* root, TreeNode* node)
{
if (root == NULL)
return false;
if (root->val == node->val)
return true;
return (inBranch(root->left, node) || inBranch (root->right, node));
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
if (root->val == p->val || root->val == q->val)
return root;
bool pInLeftBranch = false;
bool qInLeftBranch = false;
pInLeftBranch = inBranch (root->left, p);
qInLeftBranch = inBranch (root->left, q);
//Both nodes are on the left
if (pInLeftBranch && qInLeftBranch)
return lowestCommonAncestor(root->left, p, q);
//Both nodes are on the right
else if (!pInLeftBranch && !qInLeftBranch)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
在最坏的情况下，二叉树是一个长度为 N 的列表，其中每个节点最多有一个子节点，而 p 和 q 是相同的叶节点。在那种情况下，您将有一个 运行 时间 O(N^2)：您在树下的每个节点上调用 inBranch（运行时 O(N)）。
如果二叉树是平衡的，这将变成 O(N log(N))，节点 N，因为您可以将 O(2^K) 个节点放入深度为 K 的树中]（并且最多递归K次）：找到每个节点是O(N)，但你最多只做log(N)次。
请注意，更好的算法会定位每个节点一次并存储树下的路径列表，然后比较路径。找到树中的每个节点（如果是未排序的）必然是最坏的情况O(N)，列表比较也是O(N)（不平衡的情况）或O(log(N))（平衡的情况）所以总运行时间是O(N)。您可以在排序树上做得更好，但这显然不是这里给出的。
每次调用 inBranch(root, node) 时，都会添加 O（root 的后代数）（参见 time complexity of Binary Tree Search）。第一次计算时间复杂度我会假设二叉树是平衡的，然后再看树不平衡的最坏情况。
场景一：平衡树
一个节点的后代数量大约是其 parent 的一半。因此，每次我们递归时，对 inBranch 的调用都会减半。假设 N 是树中节点的总数。在对 lowestCommonAncestor 的第一次调用中，我们搜索所有 N 个节点。在随后的调用中，我们搜索左半边或右半边等等。
O(N + N/2 + N/4 ...) 是 still the same as O(N).
场景二：不平衡树
假设这棵树非常不平衡，所有 children 都在左侧：
A
/
B
/
C
/
etc...
每递归一级，后代数量只减少1。因此，我们的时间复杂度类似于：
O(N + (N-1) + (N-2) + ... + 2 + 1) 即 equivalent to O(N^2).
有没有更好的方法？
如果这是一个二叉搜索树，我们可以做到和 O(path_length(p) + path_length(q)) 一样好。如果不是，您将始终需要至少遍历整棵树一次：O(N) 以找到到每个节点的路径，但您仍然可以改进最坏的情况。我会留给你找出实际的算法！
-- 下面的 lowestCommonAncestor 函数在二叉树中找到两个节点 p 和 q 的最低公共祖先（假设两个节点都存在并且所有节点值都是独一无二）。
class Solution {
public:
bool inBranch(TreeNode* root, TreeNode* node)
{
if (root == NULL)
return false;
if (root->val == node->val)
return true;
return (inBranch(root->left, node) || inBranch (root->right, node));
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
if (root->val == p->val || root->val == q->val)
return root;
bool pInLeftBranch = false;
bool qInLeftBranch = false;
pInLeftBranch = inBranch (root->left, p);
qInLeftBranch = inBranch (root->left, q);
//Both nodes are on the left
if (pInLeftBranch && qInLeftBranch)
return lowestCommonAncestor(root->left, p, q);
//Both nodes are on the right
else if (!pInLeftBranch && !qInLeftBranch)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
在最坏的情况下，二叉树是一个长度为 N 的列表，其中每个节点最多有一个子节点，而 p 和 q 是相同的叶节点。在那种情况下，您将有一个 运行 时间 O(N^2)：您在树下的每个节点上调用 inBranch（运行时 O(N)）。
如果二叉树是平衡的，这将变成 O(N log(N))，节点 N，因为您可以将 O(2^K) 个节点放入深度为 K 的树中]（并且最多递归K次）：找到每个节点是O(N)，但你最多只做log(N)次。
请注意，更好的算法会定位每个节点一次并存储树下的路径列表，然后比较路径。找到树中的每个节点（如果是未排序的）必然是最坏的情况O(N)，列表比较也是O(N)（不平衡的情况）或O(log(N))（平衡的情况）所以总运行时间是O(N)。您可以在排序树上做得更好，但这显然不是这里给出的。
每次调用 inBranch(root, node) 时，都会添加 O（root 的后代数）（参见 time complexity of Binary Tree Search）。第一次计算时间复杂度我会假设二叉树是平衡的，然后再看树不平衡的最坏情况。
场景一：平衡树
一个节点的后代数量大约是其 parent 的一半。因此，每次我们递归时，对 inBranch 的调用都会减半。假设 N 是树中节点的总数。在对 lowestCommonAncestor 的第一次调用中，我们搜索所有 N 个节点。在随后的调用中，我们搜索左半边或右半边等等。
O(N + N/2 + N/4 ...) 是 still the same as O(N).
场景二：不平衡树
假设这棵树非常不平衡，所有 children 都在左侧：
A
/
B
/
C
/
etc...
每递归一级，后代数量只减少1。因此，我们的时间复杂度类似于：
O(N + (N-1) + (N-2) + ... + 2 + 1) 即 equivalent to O(N^2).
有没有更好的方法？
如果这是一个二叉搜索树，我们可以做到和 O(path_length(p) + path_length(q)) 一样好。如果不是，您将始终需要至少遍历整棵树一次：O(N) 以找到到每个节点的路径，但您仍然可以改进最坏的情况。我会留给你找出实际的算法！