[剑指Offer]树中两个结点的最低公共祖先 | 指尖的舞客

[剑指Offer]树中两个结点的最低公共祖先 | 指尖的舞客

题解：该题貌似简单，其实陷阱重重。首先分析了题目的陷阱：1. 题中的“树”指什么树？虽然题已经简化为二叉树，但仍然存在问题，比如说BST与普通二叉树就有区别，表示树的数据结构中是否包含指向父结点的指针；2. 给出的结点是否包含在树中（既然说已经是树中的结点了，当然包含，如此考虑只是为了增强算法的健壮性）。 思路：由于带父指针的树，问题直接可以转化为求两条链表的交点，比较简单就不细说了。 class TreeNode{ int value; TreeNode left; TreeNode right; public TreeNode(int value){ this.value = value; } } 1. 考虑BST情况，因为此类情况非常简单。 public TreeNode getLastCommonParentOfBST(TreeNode pRoot, TreeNode pNode1, TreeNode pNode2){ if(pRoot == null) return null; if(pNode1.value > pNode2.value) return getLastCommonParentOfBST(pRoot, pNode2, pNode1); TreeNode tmp = pRoot; while(tmp!=null){ if(pNode1.value>tmp.value) tmp = tmp.right; if(pNode2.value tmp.value) break; } return tmp; }   // 普通二叉树, 假设节点都在树上, 或者都不在 public TreeNode getLastCommonParent(TreeNode pRoot, TreeNode pNode1, TreeNode pNode2){ if(pRoot == null || pNode1 == pRoot || pNode2 == pRoot){ return pRoot; } TreeNode left = getLastCommonParent(pRoot.left, pNode1, pNode2);

Read full article from [剑指Offer]树中两个结点的最低公共祖先 | 指尖的舞客