BST Node Distance

Binary Search Tree

Medium

Description

Given a list of numbers, construct a BST from it(you need to insert nodes one-by-one with the given order to get the BST) and find the distance between two given nodes.

If two nodes do not appear in the BST, return -1
We guarantee that there are no duplicate nodes in BST
The node distance means the number of edges between two nodes

Example

input:
numbers = [2,1,3]
node1 = 1
node2 = 3
output:
2

Analysis

思路：

@giesekus0903

    # 构建BST
    # 求LCA
    # 计算LCA 到两点间的距离并相加，返回
    
    # build balance BST  
    # find lca of node1 and node2
    # dist(node1,lca) + dist(node2,lca)

(LintCode: Total runtime 419 ms; beats 86.80%)

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode (int v) {
            val = v;
        }
    }
    /**
     * @param numbers: the given list
     * @param node1: the given node1
     * @param node2: the given node2
     * @return: the distance between two nodes
     */
    public int bstDistance(int[] numbers, int node1, int node2) {
        // Write your code here
        TreeNode root = buildBST(numbers);
        TreeNode lca = LCA(root, node1, node2);
        int dist1 = dist(lca, node1);
        int dist2 = dist(lca, node2);
        if (dist1 < 0 || dist2 < 0) {
            return -1;
        }
        return  dist1 + dist2;
    }

    private TreeNode buildBST(int[] nums) {
        TreeNode root = new TreeNode(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            addTreeNode(root, nums[i]);
        }
        return root;
    }

    private void addTreeNode(TreeNode root, int val) {
        if (val < root.val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
            } else {
                addTreeNode(root.left, val);
            }
        } else {
            if (root.right == null) {
                root.right = new TreeNode(val);
            } else {
                addTreeNode(root.right, val);
            }
        }
    }

    private TreeNode LCA(TreeNode root, int n1, int n2) {
        /*
        if (n1 > n2) {
            return LCA(root, n2, n1);
        }
        if (n1 <= root.val && root.val <= n2) {
            return root;
        }
        if (n2 <= root.val) {
            return LCA(root.left, n1, n2);
        } else {
            return LCA(root.right, n1, n2);
        }
        */
        if (root == null) {
            return null;
        }
        if (n1 > root.val && n2 > root.val) {
            return LCA(root.right, n1, n2);
        } else if (n1 < root.val && n2 < root.val) {
            return LCA(root.left, n1, n2);
        } else {
            return root;
        }
    }

    // find depth from root to node
    private int dist(TreeNode root, int v) {
        if (root == null) {
            return -1;
        }

        if (root.val == v) {
            return 0;
        }
        if (root.val > v) {
            int left = dist(root.left, v);
            if (left < 0) {
                return -1;
            } 
            return left + 1;
        } else {
            int right = dist(root.right, v);
            if (right < 0) {
                return -1;
            } 
            return right + 1;
        }
    }

}

另一种（稍不必要的复杂了）

@yuhzeng:

先建BST, 再找LCA，两个node的距离=dist(root, n1) + dist(root, n2) - 2*dist(root, LCA). 用 findPathFromRoot来找到这三个距离。 dist = path.size() -1.

Reference

https://www.geeksforgeeks.org/shortest-distance-between-two-nodes-in-bst/