Leetcode 236.Lowest Common Ancestor of a Binary Tree

/**
 * 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:
 void seek(TreeNode* root, TreeNode* val,deque<TreeNode*>&que,deque<TreeNode*>&ans)
 {
  if(root==val)//包括自己
  {
   que.push_back(root);
   ans=que;
  }
  else
  {
   if(root->left)
   {
    que.push_back(root->left);
    seek(root->left,val,que,ans);
    que.pop_back();
   }
   if(root->right)
   {
    que.push_back(root->right);
    seek(root->right,val,que,ans);
    que.pop_back();
   }
  }
 }
 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
 {
  TreeNode*ans;
  if (root->val == p->val)return root;
  if (root->val == q->val)return root;
  //从根节点向孩子节点遍历 把拥有p和q的保留 路径上的点就是他们的爸爸 对比两个
  deque<TreeNode*> path1, path2,ans1,ans2;//分别存储根节点到p和根节点到q（其实就是p和q的爸爸 ）
  path1.push_back(root);
        seek(root,p,path1,ans1);
        path2.push_back(root);
  seek(root,q,path2,ans2);
  TreeNode* t1, *t2;
  t1 = ans1.front();
  t2 = ans2.front();
        
  while (t1==t2)
  {
   ans=t1;
            
   ans1.pop_front();
   ans2.pop_front();
   t1 = ans1.front();
   t2 = ans2.front();
  }
  return ans;
 }
};

解法：普通二叉树求公共父节点。找到根节点到两个节点的路径，路径上的点就是他的所有父亲节点，一个一个对比。求路径的方法采用回溯法，但是记得用一个ans锁定最后的答案，不然回溯之后，数据全没了。

236. Lowest Common Ancestor of a Binary Tree

Medium

1854132FavoriteShare

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]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA 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.