[LeetCode]236.Lowest Common Ancestor of a Binary Tree

本文主要是介绍[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    4Another 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;}//ifvector<TreeNode*> path1;bool isFind = Path(root,p,path1);// 没有P节点if(!isFind){return nullptr;}//ifvector<TreeNode*> path2;isFind = Path(root,q,path2);if(!isFind){return nullptr;}//ifint 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}//forreturn node;}
private:// 从根节点到node节点的路径bool Path (TreeNode* root,TreeNode* node,vector<TreeNode*> &path) {path.push_back(root);if(root == node) {return true;}//ifbool isExits = false;// 左子树if(root->left) {isExits = Path(root->left,node,path);}//if// 右子树if(!isExits && root->right) {isExits = Path(root->right,node,path);}//ifif(!isExits) {path.pop_back();}//ifreturn 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;}//ifelse{cout<<"nullptr"<<endl;}//elsereturn 0;
}