二叉樹的最近公共祖先

給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)節(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)節(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?/p>

示例 1：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3 。
示例 2：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5 。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
示例 3：

輸入：root = [1,2], p = 1, q = 2
輸出：1

提示：

樹中節(jié)點(diǎn)數(shù)目在范圍 [2, 105] 內(nèi)。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于給定的二叉樹中。

思路

后序遍歷，父節(jié)點(diǎn)會(huì)接收到子節(jié)點(diǎn)問否是p，q，并把這個(gè)狀態(tài)向上傳遞，直到滿足條件

• 返回值 節(jié)點(diǎn)
• 參數(shù) 輸入節(jié)點(diǎn)，p，q

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

• 終止條件
  節(jié)點(diǎn)==p 或 ==q 或 為空

        if(root==p || root==q || root== NULL) return root;

• 單次遞歸
  采用后序，左右中，
  左操作：設(shè)立參數(shù)left接收左子樹是否有p，q，有的話left為p或q
  右操作：設(shè)立參數(shù)right接收右子樹是否有p，q，有的話right為p或q

        TreeNode* left=lowestCommonAncestor(root->left,p,q);TreeNode* right=lowestCommonAncestor(root->right,p,q);

中操作：將本遞歸返回的參數(shù)進(jìn)行判斷，
左有q，右有p
左有p，右有q
上面一條成立，則此中節(jié)點(diǎn)為父節(jié)點(diǎn)

        if(left==NULL && right!=NULL) return right;if(left!=NULL && right==NULL) return left;if(left!=NULL && right!=NULL) return root;return NULL;

left和right的取值是靠終止條件返回，沒找到p或q，left和right就會(huì)一直是NULL

        if(root==p || root==q || root== NULL) return root;