[LeetCode]--235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______6______ / \ ___2__ ___8__ / \ / \ 0 4 7 9 / \ 3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路就是找到一个节点的所有父节点，放在一个队列里面。然后两个节点的所有父节点形成的两个队列找到分叉（最后一个相同的节点），就是最近的一个父节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; TreeNode t = null; Queue<TreeNode> q1 = new LinkedList<TreeNode>(); Queue<TreeNode> q2 = new LinkedList<TreeNode>(); seekNode(root, p, q1); seekNode(root, q, q2); while (!q1.isEmpty() && !q2.isEmpty()) { if (q1.peek().val == q2.peek().val) { t = q1.poll(); q2.poll(); } else return t; } return p; } public void seekNode(TreeNode root, TreeNode t, Queue<TreeNode> queue) { queue.offer(root); if (t.val < root.val) seekNode(root.left, t, queue); if (t.val > root.val) seekNode(root.right, t, queue); }

递归实现

// 在root为根的二叉树中找A,B的LCA: // 如果找到了就返回这个LCA // 如果只碰到A，就返回A // 如果只碰到B，就返回B // 如果都没有，就返回null public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) { if (root == null || root == node1 || root == node2) { return root; } // Divide TreeNode left = lowestCommonAncestor(root.left, node1, node2); TreeNode right = lowestCommonAncestor(root.right, node1, node2); // Conquer if (left != null && right != null) { return root; } if (left != null) { return left; } if (right != null) { return right; } return null; }