题目：
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]
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of 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.是一个普通的二叉树，不是BST，所以不能根据根节点大于其中一个结点并且小于另一个结点来判断 2.没有指向父节点的指针，所以不能直接用“寻找两个链表的第一个公共结点”来解决 3.不断遍历并判断，如果某个结点的两个子树分别包含这两个结点，但是它的某个子结点中不同时包含这两个结点，那么这个结点就是公共结点，这个方法会重复计算(大神的解法) 4.先用两个链表存储从根节点到两个子节点的路径(回溯法)，再判断路径的公共结点（这样的两个链表是从公共结点开始分叉，而不是先分叉再融合，所以判断的时候不需要双指针来回走，更加简单） 问题：二叉树结点的值有没有可能是一样的? 第一种解法，python代码：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root in (None,p,q): return root left=self.lowestCommonAncestor(root.left,p,q) right=self.lowestCommonAncestor(root.right,p,q) return root if left and right else left or rightc++代码，注意 left 和right用NULL初始化：
/** * 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*> tmp={NULL,p,q}; if (count(tmp.begin(),tmp.end(),root)) return root; TreeNode* left=NULL; TreeNode* right=NULL; if (root->left) left=lowestCommonAncestor(root->left,p,q); if(root->right) right=lowestCommonAncestor(root->right,p,q); if (left&&right) return root; else if (left) return left; else return right; } };第二种解法，由于回溯的最终结果并不是返回路径，或者把路径保存在某个结果中，所以不能用path+[new_val]的方式回溯，而应该用push()+pop()的方式，再说，在别的语言里面也没有这种直接相加的办法，只有python有，用别的语言实现回溯都是push()+pop()。 python代码：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ #不需要重新定义链表的数据结构，用一个list存储TreeNode即可 def getPath(root,node,path): if root==None: return None path.append(root) if root==node: return True found=False if not found and root.left: found= getPath(root.left,node,path) if not found and root.right: found=getPath(root.right,node,path) if not found: path.pop() return found def getLastCommonNode(path1,path2): pLast=None i=0 while i<min(len(path1),len(path2)): if path1[i]==path2[i]: pLast=path1[i] i+=1 else: break return pLast if not root or not p or not q: return None #由于不是只有一个path，所以不能用self.path，要把path作为一个参数传入函数 path1=[] path2=[] getPath(root,p,path1) getPath(root,q,path2) return getLastCommonNode(path1,path2)c++代码，学习一下用cpp实现回溯：
/** * 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,path2; bool bool1=getPath(root,path1,p); bool bool2=getPath(root,path2,q); TreeNode*lp=NULL; int i=0; while(i<min(path1.size(),path2.size())) { if (path1[i]==path2[i]) { lp=path1[i]; i+=1; } else break; } return lp; } bool getPath(TreeNode*root,vector<TreeNode*>& path,TreeNode* target) { if(!root) return NULL; path.push_back(root); bool found=false; if (root==target) return true; if (!found &&root->left) found=getPath(root->left,path,target); if(!found &&root->right) found=getPath(root->right,path,target); if (!found) path.pop_back(); return found; } };总结： python中，return a or b的意思是，当a不为空则返回a，否则返回b。
