二叉樹最近公共祖先，dfs娩井，當且僅當左子樹與右子樹都屬于一個節(jié)點或根節(jié)點為其中一個元素的情況下，找到最近公共祖先隅很。
遞歸解法 1
- Runtime: 100 ms, faster than 61.90%
- Memory Usage: 48 MB, less than 64.58%
var ans
var lowestCommonAncestor = function(root, p, q) {
dfs(root, p, q)
return ans
};
var dfs = function(root, p, q) {
if(root === null) return false
let lson = dfs(root.left, p, q)
let rson = dfs(root.right, p, q)
if((lson && rson) || ((root.val === p.val || root.val === q.val) && (lson || rson))) {
ans = root
}
return lson || rson || root.val === p.val || root.val === q.val
}
遞歸解法 2
- 時間復雜度O(N)撞牢，空間復雜度O(N)
- Runtime: 92 ms, faster than 91.28%
- Memory Usage: 48.2 MB, less than 37.96%
var lowestCommonAncestor = function(root, p, q) {
if(root === null || root === p || root === q) {
return root
}
let left = lowestCommonAncestor(root.left, p, q)
let right = lowestCommonAncestor(root.right, p, q)
if(left !== null && right !== null) {
console.log(left, right)
return root
}
return left !== null ? left : right
};
