# 【LeetCode 236】Lowest Common Ancestor of a Binary Tree

2022年11月23日
0 收藏 930 点赞 2,201 浏览 1479 个字

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）的路径（3->5 , 3->5->2->4），然后求路径序列中最后一个公共结点（5）即为所求。

C++:

` /**  * 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 { private:     vector<TreeNode* > plist; public:     void rec(TreeNode *root, TreeNode *tar, vector<TreeNode* >& res)     {         if(root == tar)         {             vector<TreeNode* >::iterator it = plist.begin();             for(; it != plist.end(); it++)                 res.push_back(*it);             return ;         }         if(root->left != )         {             plist.push_back(root->left);             rec(root->left, tar, res);             plist.pop_back();         }         if(root->right != )         {             plist.push_back(root->right);             rec(root->right, tar, res);             plist.pop_back();         }     }     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {         if(root == )             return ;         vector<TreeNode* > list1, list2;         plist.push_back(root);         rec(root, p, list1);         plist.clear();         plist.push_back(root);         rec(root, q, list2);         TreeNode  *ret = ;         vector<TreeNode* >::iterator it1 = list1.begin();         vector<TreeNode* >::iterator it2 = list2.begin();         for(; it1 != list1.end() && it2 != list2.end(); it1++, it2++)         {             if(*it1 == *it2)                 ret = *it1;         }         return ret;     } };`

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用