Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.
The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula.
Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree. 'lca' is lowest common ancestor of n1 and n2 Dist(n1, n2) is the distance between n1 and n2.
Following is C++ implementation of above approach. The implementation is adopted from last code provided in Lowest Common Ancestor Post.
/* Program to find distance between n1 and n2 using one traversal */ #include <iostream> using namespace std; // A Binary Tree Node struct Node { struct Node *left, *right; int key; }; // Utility function to create a new tree Node Node* newNode(int key) { Node *temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } // Returns level of key k if it is present in tree, otherwise returns -1 int findLevel(Node *root, int k, int level) { // Base Case if (root == NULL) return -1; // If key is present at root, or in left subtree or right subtree, // return true; if (root->key == k) return level; int l = findLevel(root->left, k, level+1); return (l != -1)? l : findLevel(root->right, k, level+1); } // This function returns pointer to LCA of two given values n1 and n2. // It also sets d1, d2 and dist if one key is not ancestor of other // d1 --> To store distance of n1 from root // d2 --> To store distance of n2 from root // lvl --> Level (or distance from root) of current node // dist --> To store distance between n1 and n2 Node *findDistUtil(Node* root, int n1, int n2, int &d1, int &d2, int &dist, int lvl) { // Base case if (root == NULL) return NULL; // If either n1 or n2 matches with root's key, report // the presence by returning root (Note that if a key is // ancestor of other, then the ancestor key becomes LCA if (root->key == n1) { d1 = lvl; return root; } if (root->key == n2) { d2 = lvl; return root; } // Look for n1 and n2 in left and right subtrees Node *left_lca = findDistUtil(root->left, n1, n2, d1, d2, dist, lvl+1); Node *right_lca = findDistUtil(root->right, n1, n2, d1, d2, dist, lvl+1); // If both of the above calls return Non-NULL, then one key // is present in once subtree and other is present in other, // So this node is the LCA if (left_lca && right_lca) { dist = d1 + d2 - 2*lvl; return root; } // Otherwise check if left subtree or right subtree is LCA return (left_lca != NULL)? left_lca: right_lca; } // The main function that returns distance between n1 and n2 // This function returns -1 if either n1 or n2 is not present in // Binary Tree. int findDistance(Node *root, int n1, int n2) { // Initialize d1 (distance of n1 from root), d2 (distance of n2 // from root) and dist(distance between n1 and n2) int d1 = -1, d2 = -1, dist; Node *lca = findDistUtil(root, n1, n2, d1, d2, dist, 1); // If both n1 and n2 were present in Binary Tree, return dist if (d1 != -1 && d2 != -1) return dist; // If n1 is ancestor of n2, consider n1 as root and find level // of n2 in subtree rooted with n1 if (d1 != -1) { dist = findLevel(lca, n2, 0); return dist; } // If n2 is ancestor of n1, consider n2 as root and find level // of n1 in subtree rooted with n2 if (d2 != -1) { dist = findLevel(lca, n1, 0); return dist; } return -1; }
Time Complexity: Time complexity of the above solution is O(n) as the method does a single tree traversal.
From:
相关推荐
BinaryTree-BinaryTree
This is a binary tree search implementation.
binary tree 的C语言实现算法,需要在linux环境下编译
BinaryTree-源码.rar
懂的人自然懂:) 用C#写的binarytree
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal ...
2.binaryTree树 标准的二叉树。 实现了各种算法,增删查改等等
For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5...
心希盼 C++ STL 二叉树 详细请看“心希盼 binaryTree.doc”
BinaryTreeSort的java实现,简单的二叉树排序
二叉树的实现,各种方法,构造函数,析构函数,前序遍历,中序遍历,后续遍历,层次序遍历
constructing a binary tree
BinaryTree: 用于学习二叉树的Python库
C++实现 操作函数包括先序、中序、后序遍历,求深度,深度、广度遍历 构建二叉树
有序二叉树创建 有序二叉树查找 二叉树遍历 有序二叉树删除 类模版实现的有序二叉树
二叉树的实现代码,我的博客“Java——二叉树的基础实现”的代码。 https://blog.csdn.net/J_fla/article/details/103236673
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal ...
二叉树前序遍历,leetcode
数据结构教学课件:chapter5 A Binary Tree Node ADT.ppt