fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits.h>
  4. using namespace std;
  5.  
  6. struct Node{
  7.     int val;
  8.     struct Node *left, *right;
  9.     Node(int v): val(v), left(NULL), right(NULL){}
  10. };
  11.  
  12. struct Node* buildTree(int nums[], int arrsize, int *index, int min, int max){
  13.     if (*index > arrsize || *index < 0) return NULL;
  14.  
  15.     Node* root =  NULL;
  16.     int val = nums[*index];
  17.     if (val < max && val > min){
  18.         root = new Node(val);
  19.         ++(*index);
  20.         if (*index < arrsize){
  21.             root->left = buildTree(nums, arrsize, index, min, val);
  22.             root->right = buildTree(nums, arrsize, index, val, max);
  23.         }
  24.  
  25.     }
  26.     return root;
  27. }
  28.  
  29. struct Node* constructBST(int nums[], int arrsize){
  30.     int idx = 0;
  31.     return buildTree(nums, arrsize, &idx, INT_MIN, INT_MAX);
  32. }
  33.  
  34. bool findPath(Node *root, vector<int>& path, int val){
  35.     if (!root) return false;
  36.     path.push_back(root->val);
  37.  
  38.     if (root->val == val) return true;
  39.  
  40.     if( (root->left && findPath(root->left, path, val) ) ||
  41.         (root->right && findPath(root->right, path, val)))
  42.         return true;
  43.     path.pop_back();
  44.     return false;
  45. }
  46. int getDistance(Node *root, int node1, int node2){
  47.     vector<int> path1, path2;
  48.     if (!findPath(root,path1,node1) || !findPath(root,path2,node2))
  49.         return 0;
  50.     int common_node = 0;
  51.     for (int i = 0; i < path1.size() && path2.size(); ++i){
  52.         if (path1[i] != path2[i]) break;
  53.         ++common_node;
  54.     }
  55.     cout << path1.size() << "; " <<  path2.size() << "; " << common_node << endl;
  56.     return (path1.size() + path2.size() - 2 * common_node);
  57. }
  58. int main() {
  59. 	//code
  60. 	int nums[] = {5,6,3,1,2,4};
  61. 	int arrsize = sizeof(nums)/sizeof(nums[0]);
  62.  
  63. 	Node *root = constructBST(nums, arrsize);
  64.  
  65. 	cout << "The distance is " << getDistance(root, 4,6) << endl;
  66.  
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The distance is 0
https://ideone.com/8kqKG4
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!