问题
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree
寻找二叉树中两个节点最近的公共祖先结点
思路
方法 1
按照两个节点和 root 的关系进行分类
两个节点一个在 root 左边，另一个在 root 右边，显然它们的公共祖先节点就是 root
两个节点都在 root 左边，以 root.left 为新 root 递归求解
两个节点都在 root 右边，以 root.right 为新 root 递归求解
该方法需要耗费时间来确定两个节点所处的位置，效率不高
方法 2
参考老外的 post，不 "显式" 地计算两个节点所处的位置
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); return left == null ? right : right == null ? left : root;}