Binary Search Tree Path

Binary search tree path：

Given the root of a binary search tree and two values, write a function that returns the path between the two values.

Code

综合题：先找到LCA，再向左向右找到path,合并。

We can reuse the code that we wrote in the least common ancestor problem, because the least

common ancestor will be the root of our path. Once we have the least common ancestor, we can

simply build a path to the value on the right, and a path to the value on the left, and combine the two to

get the path between the two nodes.

Complexity:

Time: O(n) where n is the length of the path

Space: O(n)

public static List<TreeNode> findShortestPath(TreeNode head, int x, int y) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if (root == null) {
            return result;
        }
        TreeNode common = LCA(head, x, y);
        List<TreeNode> left = findPath(common, x);
        List<TreeNode> right = findPath(common, y);
        //这里判断x,y大小来确定哪个是左边的路径，并把左边的最后一个节点remove掉，因为会和右边第一个重复。
        if (x < y) {
            left.remove(left.size()-1);
            result.addAll(left);
            result.addAll(right);
        }else{
            right.remove(right.size()-1);
            result.addAll(right);
            result.addAll(left);
        }
        return result;
    }

    public TreeNode LCA(TreeNode root, int x, int y) {
        if (root == null) {
            return root;
        }
        if (root.val > x && root.val >y) {
            return LCA(root.left, x, y);
        }
        else if (root.val < x && root.val < y) {
            return LCA(root.right, x, y);
        }
        else
            return root;
    }

    public List<TreeNode> findPath(TreeNode root, int x) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if (root.val == x) {
            result.add(root);
            return result;
        }
        //注意顺序，先把左边的加进去最后加root.
        if (root.val > x) {
            List<TreeNode> left = findPath(root.left, x);
            result.addAll(left);
            result.add(root);
        }
        //注意顺序，先加进root,再把right加进去。
        if (root.val < x) {
            result.add(head);
            List<TreeNode> right = findPath(root.right, x);            
            result.addAll(right);
        }
        return result;
    }