题目描述:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
解析:
1.如果根节点为空或者根节点等于p或q,直接返回根节点即可
2.定义节点pqInLeft,pqInRight
3.分为三种情况
左子树中没有p,q的值,则返回右子树的节点pqInRight
右子树中没有p,q的值,则返回左子树的节点pqInLeft
p,q分别在左右子树中,则返回根节点
Java:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) { return root; } TreeNode pqInLeft = lowestCommonAncestor(root.left, p, q); TreeNode pqInRight = lowestCommonAncestor(root.right, p, q); if(pqInLeft == null) { return pqInRight; } else if(pqInRight == null) { return pqInLeft; } else { return root; } }
JavaScript:
var lowestCommonAncestor = function(root, p, q) { if(root === null || root === p || root === q) { return root; } let pqInLeft = lowestCommonAncestor(root.left, p, q); let pqInRight = lowestCommonAncestor(root.right, p, q); if(pqInLeft === null) { return pqInRight; } else if(pqInRight === null) { return pqInLeft; } else { return root; } };