[LeetCode]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 thedefinition 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 allowa node to be a descendant of itself).”

_______3______/\___5_____1__ /\/\ 6_208/ \7 4

For example, the lowest common ancestor (LCA) of nodes5and1is3. Another example is LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.

［思路］

深度优先搜索搜寻节点，，存储节点路径。在两个路径中找到公共节点。注意不是二叉搜索树。

［代码］

/** * Definition for a binary tree node. * 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*> path1;vector<TreeNode*> path2;TreeNode* ret;FindPath(root,path1,p);FindPath(root,path2,q);for(int i=0 ;i<min(path1.size(),path2.size());++i){if(path1[i]==path2[i])ret = path1[i];}return ret;}void FindPath(TreeNode *root,vector<TreeNode*> &path,TreeNode *find){if(root == nullptr){return;}if(root == find){path.push_back(find);return;}path.push_back(root);FindPath(root->left,path,find);FindPath(root->right,path,find);path.pop_back();}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。