查找二叉树的两个节点之间的距离


难度级别 易得奖学金
经常问 亚马逊 LinkedIn MakeMyTrip Netflix公司 Samsung
二叉树

问题陈述

问题“查找二叉树的两个节点之间的距离”指出,给您一个二叉树,并且给了您两个节点。 现在,您需要找到这两个节点之间的最小距离。

使用案列

查找二叉树的两个节点之间的距离

// Tree is shown using the image above
node 1 = 9
node 2 = 4
3

查找二叉树的两个节点之间的距离的方法

问题要求找到二叉树的两个节点之间的距离。 因此,我们将获得两个节点以及一个二叉树和两个节点。 现在我们需要找到这两个节点之间的最小距离。 这是二叉树上的经典问题,通常在n元树中。 我们使用 最小共同祖先 的树。 最小公共祖先或LCA是距离两个节点至少最小的节点,并且位于从这些节点到树的根的路径上。 但是此LCA如何帮助我们计算最小距离?

最小距离的路径始终通过两个节点的LCA。 因此,如果我们以某种方式知道两个节点到根的距离以及它们的LCA到根的距离。 我们可以计算一个简单的公式来找到最小距离。 我们将两个节点到根的距离相加,然后从树的根减去它们的LCA距离的两倍。 所以在

代码

C ++代码打印二叉树的底部视图

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

// calculates distance for the node from the root
int findDistUtil(node* root, int n, int lev){
    if(!root)
        return -1;
    if(root->data == n)
        return lev;
    else{
        int left = findDistUtil(root->left, n, lev+1);
        int right = findDistUtil(root->right, n, lev+1);
        return (left != -1) ? left : right;
    }
}

node* findLCA(node* root, int n1, int n2){
    if(!root)
        return NULL;
    if(root->data == n1 || root->data == n2){
        return root;
    } else {
        // check if leftSubTree has n1 or n2 or both
        node* leftSubTree = findLCA(root->left, n1, n2);
        // check if rightSubTree has n1 or n2 or both
        node* rightSubTree = findLCA(root->right, n1, n2);
        if(leftSubTree && rightSubTree)
            return root;
        // if we don't find one nodes in left and one node in right subtree
        // then the lca must be either in left subtree or right subtree
        return (leftSubTree != NULL) ? leftSubTree : rightSubTree;
    }
}

int computeMinDistance(node* root, int n1, int n2){
    node* lca = findLCA(root, n1, n2);
    int n1dist = findDistUtil(root, n1, 0);
    int n2dist = findDistUtil(root, n2, 0);
    int lcadist = findDistUtil(root, lca->data, 0);
    return n1dist + n2dist - 2*lcadist;
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  cout<<computeMinDistance(root, 9, 4);
}
3

Java代码以打印二叉树的底部视图

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  // calculates distance for the node from the root
  static int findDistUtil(node root, int n, int lev){
      if(root == null)
          return -1;
      if(root.data == n)
          return lev;
      else{
          int left = findDistUtil(root.left, n, lev+1);
          int right = findDistUtil(root.right, n, lev+1);
          return (left != -1) ? left : right;
      }
  }

  static node findLCA(node root, int n1, int n2){
      if(root == null)
          return null;
      if(root.data == n1 || root.data == n2){
          return root;
      } else {
          // check if leftSubTree has n1 or n2 or both
          node leftSubTree = findLCA(root.left, n1, n2);
          // check if rightSubTree has n1 or n2 or both
          node rightSubTree = findLCA(root.right, n1, n2);
          if(leftSubTree != null && rightSubTree != null)
              return root;
          // if we don't find one nodes in left and one node in right subtree
          // then the lca must be either in left subtree or right subtree
          return (leftSubTree != null) ? leftSubTree : rightSubTree;
      }
  }

  static int computeMinDistance(node root, int n1, int n2){
      node lca = findLCA(root, n1, n2);
      int n1dist = findDistUtil(root, n1, 0);
      int n2dist = findDistUtil(root, n2, 0);
      int lcadist = findDistUtil(root, lca.data, 0);
      return n1dist + n2dist - 2*lcadist;
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    System.out.print(computeMinDistance(root, 9, 4));
  }
}
3

复杂度分析

时间复杂度

上), 即使该树被遍历了多次。 但这并不构成多项式时间复杂度。 一种操作是找到在O(N)时间中完成的两个节点的LCA。 然后我们发现节点到根的距离,这再次是在O(1)时间完成的。 这使“二叉树的两个节点之间的查找距离”问题在时间复杂度方面呈线性关系。

空间复杂度

哦), 编译器堆栈需要此空间。 因为所有函数都是递归函数,将使用 递归 .