Leetcode-236Lowest Common Ancest

236. 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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

题解：

输入一个二叉树并给定两个二叉树上的节点，求这两个节点的最近公共祖先；
例如，输入二叉树；

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

求图中红圈标记的节点13，节点5的最近公共祖先；

首先，我们要递归深度优先搜索二叉树，找到节点13和节点5的路径，可以得到：
节点13路径：5->8->13；
节点5路径： 5->8->4->5；
发现两个节点的公共祖先为 5->8，也就是节点13和节点5的路径中相同的部分；那么最近公共祖先就是5->8中离两个节点最近的节点，所以输出节点8；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

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) {
        vector<TreeNode *> path;
        vector<TreeNode *> p_path;
        vector<TreeNode *> q_path;
        TreeNode *result = NULL;
        int search = 0;
        getPath(root, p, path, p_path, search);
        search = 0;
        //path.clear();
        getPath(root, q, path, q_path, search);
        for (int i = 0; i < min(p_path.size(), q_path.size()); i++) {
            if (p_path[i] == q_path[i]) {
                result = p_path[i];
            }
            else {
                break;
            }
        }
        return result;
    }
private:
    void getPath(TreeNode *root, TreeNode *node, vector<TreeNode *> &path, vector<TreeNode *> &result, int &search) {
        if (!root || search == 1) {
            return;
        }
        path.push_back(root);
        if (root == node) {
            result = path;  //不专门存储node的path的话，等递归返回到第一层的时候path 就没啦！
            search = 1;  //说明已经找到了节点node所在的位置，可以结束递归啦；
         //注，search的形参一定要引用&传递，不然会在一层递归结束后直接释放啦！ 
        }
        getPath(root->left, node, path, result, search);
        getPath(root->right, node, path, result, search);
        path.pop_back();
    }
};

int main() {
    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode i(5);
    TreeNode j(1);
    a.left = &b;
    b.left = &d;
    d.left = &g;
    d.right = &h;
    a.right = &c;
    c.left = &e;
    c.right = &f;
    f.left = &i;
    f.right = &j;
    Solution s;
    TreeNode *result;
    result = s.lowestCommonAncestor(&a, &e, &i);
    printf("%d ", result->val);
    return 0;
}

结果：

8

My Solution(Python)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if self.root_judge(p, q):
                return p
            elif self.root_judge(q, p):
                return q
            elif self.root_judge(root.left, p) and self.root_judge(root.left, q):
                root = root.left
            elif self.root_judge(root.right, p) and self.root_judge(root.right, q):
                root = root.right
            else:
                return root
        return root
       
    def root_judge(self, root, child):
        if not root:
            return False
        if root == child:
            return True
        return self.root_judge(root.left, child) or self.root_judge(root.right, child)