网络异常，图片无法展示
|
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 复制代码
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 复制代码
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 复制代码
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。 复制代码
解题思路
从上向下的递归遍历二叉树，如果当前节点为空，终止递归，并返回 false。
获取左右子树的回溯结果，如果说当前节点是目标节点之一并且左子树返回值为真或者右子树返回值为真，说明当前节点是一个目标节点，并且在左子树或者右子树找到了另外一个目标节点，那么当前节点就是要找的最近公共祖先。
或者当前节点不是某一个目标节点，但是左子树返回值为真，并且右子树返回值为真，则说明在左子树中找到了一个目标值，并且在右子树找到了一个目标值，那么当前节点就是要找的最近的公共祖先。
向上回溯当前节点的返回值的时候，就需要判断当前节点是否是目标节点，或者左子树返回值为真，或者右子树返回值为真，如果以上条件成立，则返回值为 true, 否则返回 false。
动画演示
网络异常，图片无法展示
|
代码实现
var lowestCommonAncestor = function(root, p, q) { // 创建变量保存结果值 let res; // 后续遍历二叉树 function postorder(node){ // 如果当前节点为空，返回false if(node === null) return false; // 获取左右子树返回值 const l = postorder(node.left), r = postorder(node.right); if( // 如果当前节点为目标节点，并且在左子树或者右子树中找到了另一个目标节点，则当前节点为最近的公共祖先 (node === p || node === q)&&(l || r) || // 如果左子树找到了一个目标节点，并且右子树找到了另一个目标节点，则当前节点为最近的公共祖先 (l && r) ){ res = node; } // 如果当前节点为目标节点，或者其子树中找到了目标节点，返回 true,否则返回 false return node === p || node === q || l || r || false } postorder(root); return res; }; 复制代码
至此我们就完成了 leetcode-面试题 04.08-首个共同祖先
如有任何问题或建议，欢迎留言讨论！
