[LeetCode]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


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.

代码

/*---------------------------------------
*   日期：2015-07-13
*   作者：SJF0115
*   题目: 236.Lowest Common Ancestor of a Binary Tree
*   网址：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
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 == nullptr || p == nullptr || q == nullptr){
            return nullptr;
        }//if
        vector<TreeNode*> path1;
        bool isFind = Path(root,p,path1);
        // 没有P节点
        if(!isFind){
            return nullptr;
        }//if
        vector<TreeNode*> path2;
        isFind = Path(root,q,path2);
        if(!isFind){
            return nullptr;
        }//if
        int size1 = path1.size();
        int size2 = path2.size();
        // 求最近祖先
        TreeNode* node = nullptr;
        for(int i = 0,j = 0;i <= size1 && j <= size2;++i,++j){
            if((i == size1 || j == size2) || path1[i] != path2[j]){
                node = path1[i-1];
                break;
            }//if
        }//for
        return node;
    }
private:
    // 从根节点到node节点的路径
    bool Path (TreeNode* root,TreeNode* node,vector<TreeNode*> &path) {
        path.push_back(root);
        if(root == node) {
            return true;
        }//if
        bool isExits = false;
        // 左子树
        if(root->left) {
            isExits = Path(root->left,node,path);
        }//if
        // 右子树
        if(!isExits && root->right) {
            isExits = Path(root->right,node,path);
        }//if
        if(!isExits) {
            path.pop_back();
        }//if
        return isExits;
    }
};

int main(){
    Solution s;
    TreeNode* root = new TreeNode(3);
    TreeNode* node1 = new TreeNode(0);
    TreeNode* node2 = new TreeNode(1);
    TreeNode* node3 = new TreeNode(2);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node6 = new TreeNode(6);
    TreeNode* node7 = new TreeNode(7);
    TreeNode* node8 = new TreeNode(8);
    root->left = node5;
    root->right = node2;
    node5->left = node6;
    node5->right = node3;
    node3->left = node7;
    node3->right = node4;
    node2->left = node1;
    node2->right = node8;
    TreeNode* node = s.lowestCommonAncestor(root,node7,node1);
    if(node != nullptr){
        cout<<node->val<<endl;
    }//if
    else{
        cout<<"nullptr"<<endl;
    }//else
    return 0;
}

运行时间