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