Leetcode之236. Lowest Common Ancestor of a Binary Tree Medium

236. Lowest Common Ancestor of a Binary Tree Medium

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

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).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

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.

Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.

分析：

首先，树的问题，往往涉及递归，之所以涉及递归是因为每一棵树都是由相同结构的多个子树构成。本题可以利用递归的方式，相当于从叶子节点开始，递归地返回如下信息：当前树（或子树）同时包含p和q，则函数返回的结果就是它们的最低公共祖先。如果它们其中之一在子树当中，则结果是它们中的一个。如果它们都不在子树里，则结果返回NULL。

class Solution {
public:
    TreeNode * lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 虽然下面两个if可以写到一起，但所表达的意思是不一样的
        if (root == nullptr) {
            return nullptr;
        }
        if (p == root || q == root) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left == nullptr) {  // 如果有一个分支为空，另一个不为空，则返回不为空的节点
            return right;
        }
        else if (right == nullptr) {
            return left;
        }
        else  // 如果两个都不为空，则返回二者当前最低祖先节点
            return root;
    }
};

总结：

书上对这道题的做法麻烦了。首先书上并不是二叉树，而是一颗普通树，所以next存在一个vector里。
其次，书上的做法是先找到p和q两条路径，从根节点出发到p和q分别构成两条链表；
最后，寻找这两条链表的第一个分叉的地方。

注：

如果本题的树是二叉搜索树或者有指向父节点的指针，则思路能更加简单。

1）如果是二叉搜索树，我们只需要从树的根节点开始和两个输入节点进行比较，如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点；反之，则遍历右子节点。这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低公共祖先。

2）如果是一棵普通的树，但有指向父节点的指针，此时问题可以换成求两个链表的第一个公共节点。

3）书上面试者提供的从上至下遍历子树的思路相同，其实并不好，因为会涉及到某些结点的多次遍历，一方面我觉得可以利用类似动态规划的方法存储不同节点的遍历结果信息（如用一个字典），下次再用到的时候直接返回结果即可。另一方面，和面试者提出的优化方法一样，利用辅助空间，将从根节点到输入的两个节点的路径分别用两个链表保存，然后将问题转化为两个链表最后公共节点（和注释2类似）。链表的实现用的是C++ list，如：list<TreeNode*> path1。本题是另一种优化思路，自底向上，这样避免了多次遍历相同节点，保证了每个节点只遍历一次。（有一种动态规划的思想）

书上思路如下：

面试者是这么解释这个思路的：所谓两个节点的公共祖先，指的是这两个节点都出现在某个节点的子树中。我们可以从根节点开始遍历一棵树，每遍历到一个节点时，判断两个输入节点是不是在它的子树中。如果在子树中，则分别遍历它的所有子节点，并判断两个输入节点是不是在它们的子树中。这样从上到下一直找到的第一个节点，它自己的子树同时包含两个输入的节点而它的子节点却没有，那么该节点就是最低公共祖先。