Leetcode_236_Lowest Common Ancestor of a Binary Tree

[lihe]

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.

题意：给定二叉树和两个数，找出两个数的最近公共祖先。

解题思路：

1. 从根节点遍历至该节点，找到节点后就结束搜索；
2. 将遍历过程中遇见的节点按照顺序存储起来，这些节点即为路径；
3. 最近公共祖先即为从根节点到q和p的路径上最后一个相同节点。

void preorder(TreeNode* node, TreeNode* search,
        std::vector<TreeNode*> &path, std::vector<TreeNode*> &result, int &finish){
    if(!node || finish){
        return;
    }
    path.push_back(node);
    if(node == search){
        finish = 1;
        result = path;
    }
    preorder(node -> left, search, path, result, finish);
    preorder(node -> right, search, path, result, finish);
    path.pop_back();
}

class Solution{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
        std::vector<TreeNode*> path;
        std::vector<TreeNode*> node_p_path;
        std::vector<TreeNode*> node_q_path;

        int finish = 0;
        preorder(root, p, path, node_p_path, finish);
        path.clear();
        finish = 0;
        preorder(root, q, path,node_q_path, finish);
        int path_len = 0;
        if(node_p_path.size() < node_q_path.size()){
            path_len = node_p_path.size();
        }
        else{
            path_len = node_q_path.size();
        }
        TreeNode* result = 0;
        for(int i = 0; i < path_len; i++){
            if(node_p_path[i] == node_q_path[i]){
                result = node_p_path[i];
            }
        }
        return result;
    }
};