检查BST的每个内部节点是否恰好有一个子节点


难度级别 易得奖学金
经常问 Accenture 亚马逊 单排解决方案 贝宝 新思
二进制搜索树 二叉树

问题陈述

“检查BST的每个内部节点是否恰好有一个孩子”问题指出,您已获得对二进制搜索树的预遍历。 并且您需要查找所有非叶节点是否仅包含一个子节点。 在这里,我们还认为给定输入中的所有节点都具有不同的值。

使用案列

检查BST的每个内部节点是否恰好有一个子节点

 

Preorder Traversal: 6 15 7 9 11
Yes

说明: 如上图所示,具有给定预遍历的树的每个内部节点都有一个子节点。 因此输出为是。

检查BST的每个内部节点是否恰好有一个子节点的方法

预购遍历 表示优先选择根,并在其左子树和右子树之前打印根。 因此,根之后的元素小于或大于根。 因此,如果我们需要检查给定序列是否为 二进制搜索树。 我们可以使用两个嵌套循环来检查是否可以创建具有给定序列的二叉搜索树。

天真的方法

正如我们已经讨论的那样,预遍历包含顶部的根以及打印左右子树之后的根。 现在完成此操作 递归地 直到树中的所有节点都被覆盖为止。 因此,我们可以检查给定的序列是否代表BST,我们运行两个嵌套循环,其中使用外部循环选择根。 嵌套循环检查其后面的元素是否可以表示其左子树和右子树。 为此,我们检查直到某个索引之前所有元素都小于所选择的元素。 之后的元素大于所选择的元素。 现在,我们可以根据用例修改此方法。

让我们看看如何修改算法,以检查BST的每个内部节点是否恰好有一个子节点。 如果BST的内部孩子正好有一个孩子。 这意味着每个内部节点可以具有左子树或右子树。 它不会同时包含两个子树。 因此,总结一下我们的算法。 我们使用两个嵌套循环,其中外部循环拾取一个元素。 然后,使用嵌套循环检查其后的元素是否属于任何子树。 以前,我们曾经有一个确定的索引,在此索引之前,元素小于根,之后的元素大于根。 现在,我们找不到任何这样的索引。 但是该方法效率不高,因为它的多项式时间复杂度为O(N ^ 2)。

高效的方法

到目前为止,我们已经明确指出,根据此问题,任何节点的所有子节点将小于或大于当前节点。 因此,要检查BST的每个内部节点是否恰好有一个子节点,我们找到当前节点的下一个预购后继者。 然后,我们找到当前节点的最后一个预购后继。 如果两个后继者都小于当前节点或大于当前节点。 然后我们继续进行其他操作,我们知道当前节点同时具有左右子树,因为其中一个元素小于当前节点。 并且另一个节点大于当前节点。 因此,根据我们的要求,我们返回false或-1。

代码

C ++代码检查BST的每个内部节点是否恰好有一个子节点

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

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

Java代码,用于检查BST的每个内部节点是否恰好有一个子节点

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

复杂度分析

时间复杂度

O(N),因为我们刚刚遍历了预排序数组。 前置数组具有N个元素,因此线性时间复杂度。

空间复杂度

O(N),即递归堆栈所需的空间,我们还使用大小为N的输入数组存储预排序序列。