二叉樹的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
思路：
一開始看到這個題目的反應(yīng)是盼产，如果可以從p，q節(jié)點往上搜索就好了兆旬。于是想到了對于二叉樹的后序遍歷灵临，二叉樹的后序遍歷返回時需要攜帶信息表示以該節(jié)點為根的子樹是否包含需要尋找的節(jié)點p或q拔创，或者是返回已經(jīng)找到的最近公共祖先威始。我們?nèi)ミf歸的查找：
base case：
1.root為null短绸，直接返回null鼻吮；
2.root為p或q育苟，直接返回root。
other case：
1.當root的左子樹遍歷后返回的不為null椎木，且root的右子樹遍歷后返回的也不為null時违柏，代表root即最近公共祖先。
2.當root的左子樹后序遍歷返回結(jié)果或右子樹后序遍歷返回結(jié)果其中之一為null香椎，另外一個不為null的時候漱竖，代表在以root為根的子樹中包需要尋找的p/q節(jié)點，也有可能這個節(jié)點就是最近公共祖先節(jié)點畜伐，那么繼續(xù)向上返回這個節(jié)點馍惹。
3.當root的左子樹后序遍歷返回結(jié)果為null，同時root右子樹后序遍歷返回結(jié)果也為null，那么代表以該root為根節(jié)點的樹上沒有要找的節(jié)點万矾，于是也向上傳遞null悼吱。
代碼：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root == p || root == q) return root;
TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
TreeNode rightResult = lowestCommonAncestor(root.right, p, q);
if(leftResult!=null && rightResult!=null){
return root;
}
if(leftResult==null && rightResult==null){
return null;
}
return leftResult==null ? rightResult : leftResult;
}
}
