首页 > 试题广场 >

根据后序数组重建搜索二叉树

[编程题]根据后序数组重建搜索二叉树
  • 热度指数:1973 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个有 n 个不重复整数的数组 arr,判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。

输入描述:
第一行一个整数 n,表示数组的长度。

第二行 n 个整数 arr_i。


输出描述:
如果是搜索二叉树后序遍历的结果则输出 "true",否则输出 "false"。
示例1

输入

3
1 3 2

输出

true

备注:

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
        }
        System.out.println(isPost(array, 0, array.length - 1));
    }

    /*
    0 <= first <= last < array.length
     */
    private static boolean isPost(int[] array, int first, int last) {
        int less = first - 1;
        int more = last;
        for (int i = first; i < last; i++) {
            if (array[i] < array[last]) {
                less = i;
            } else {
                more = more == last ? i : more;
            }
        }
        return less + 1 == more
                && (less < first || isPost(array, first, less))
                && (more == last || isPost(array, more, last - 1));
    }
}
思路:
1.序列结构特点
若一个输入序列是某个二叉搜索树的后序遍历序列
等价于
输入序列的格式满足如下格式:|左子树的后序遍历序列|右子树的后序遍历序列|根节点|
2.判断条件
由于:
二叉搜索树的性质:左子树中所有节点 < 根节点 & 右子树中所有节点 > 根节点
所以:
左子树最后一个节点的偏移量 + 1 == 右子树第一个节点的偏移量
编辑于 2020-06-21 22:11:04 回复(0)
二叉搜索树后序遍历的最后一个节点为根节点,且左子树的节点值均小于根节点值,右子树的节点值均大于根节点值。对于某棵用数组arr描述的子树,我们可以检查一下数组中有多少个小于根节点的节点,记为leftNums。检查左子树arr[0: leftNums]是不是都小于根节点,右子树arr[leftNums: arr.length - 1]是不是都大于根节点。然后递归检查左右子树是不是都满足这一规律。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n];
        String[] str = br.readLine().split(" ");
        for(int i = 0; i < n; i++) seq[i] = Integer.parseInt(str[i]);
        int leftNums = seq[seq.length - 1];
        leftNums --;     // 左子树节点数
        System.out.println(isBST(leftNums, seq));
    }
    
    private static boolean isBST(int leftNums, int[] seq) {
        if(leftNums <= 0 || seq.length == 1) return true;       // 只有一个节点或没有左子树了直接返回true
        int rootVal = seq[seq.length - 1];       // 当前子树根节点值
        // 左子树有比根节点值大的节点就返回false
        for(int i = 0; i < leftNums; i++)
            if(seq[i] >= rootVal) return false;
        // 右子树有比根节点小的节点也返回false
        for(int i = leftNums; i < seq.length - 1; i++)
            if(seq[i] <= rootVal) return false;
        int[] leftTree = Arrays.copyOfRange(seq, 0, leftNums);
        int[] rightTree = Arrays.copyOfRange(seq, leftNums, seq.length - 1);
        // 左右子树都要是BST
        return isBST(getLeftNums(leftTree), leftTree) && isBST(getLeftNums(rightTree), rightTree);
    }
    
    // 计算比根节点小的节点数
    private static int getLeftNums(int[] nums) {
        int count = 0;
        for(int i = 0; i < nums.length - 1; i++)
            if(nums[i] < nums[nums.length - 1]) count ++;
        return count;
    }
}

发表于 2021-11-16 17:08:31 回复(0)
#判断当前序列是否是二叉搜索树后序遍历
#二叉搜索树的特点是左子树小于根,右子树大于根
#而后序遍历是左右根的顺序
#所以序列应该是从小到大的顺序
def isBST(nums, low, high) -> bool:
    #叶节点
    if low >= high:
        return True
    #根节点
    last = nums[high]
    i = 0
    #找到右子树入口
    for i in range(low, high):
        if nums[i] > last:
            break
    #在右子树中判断
    #右子树中的节点值应该是大于根节点值的
    for j in range(i + 1, high):
        #违反了规定
        #一定不是
        if nums[j] < last:
            return False
    #分别在两棵子树中递归进行判断
    return isBST(nums, low, i - 1) and isBST(nums, i, high - 1)

n = eval(input())
nums = list(map(int, input().split()))
rlt = isBST(nums, 0, len(nums) - 1)
if rlt:
    print('true')
else:
    print('false')

发表于 2021-08-05 09:13:26 回复(0)
import java.util.*;

class Node {
    public int val;
    public Node right;
    public Node left;
    public Node (int data) {
        this.val = data;
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        boolean res = testBST(arr);
        System.out.println(res);
    }
    
    public static boolean testBST(int[] arr) {
        if (arr == null || arr.length == 0)
            return false;
        return isPost(arr, 0, arr.length-1);
    }
    
    //检测是否可能组成二叉树后序排列
    public static boolean isPost(int[] arr, int start, int end) {
        if (start == end)
            return true;
        int less = start-1;
        int more = end;
        //找最后一个小于自己和大于自己的index
        for (int i = start; i < end; i++) {
            if (arr[end] > arr[i]) {
                less = i;
            }
            else {
                more = more == end ? i : more;
            }
        }
        //如果不满足左边小右边大,则直接返回false
        if (less != more - 1) {
            return false;
        }
        //如果列数组中所有数都比root小或都比root大,则检查子树
        if (less == start-1 || more == end)
            return isPost(arr, start, end-1);
        return isPost(arr, start, less) && isPost(arr, more, end-1);
    }
}

发表于 2021-06-18 23:17:02 回复(0)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        System.out.println(isPostOrder(arr, 0, n-1));
		
	}
	
	
	private static boolean isPostOrder(int arr[],int start,int end) {
		if(start >=end) return true;
		// 记录根节点的值,搜索二叉树的根节点必须满足左 <根<右
		int rootVal = arr[end];
		boolean flag = false;
		int mid = end;
        // 找到第一个比根节点大的值,且必须满足之后的节点也大于根节点
		// 记录第一个比根节点大的值的下标,此为左右数组划分的位置
		for(int i=start;i<end;i++) {
			if(!flag && arr[i]>rootVal) {
				mid = i;
				flag = true;
			}else if(flag && arr[i]<rootVal) {
				return false;
			}
		}
		
		return isPostOrder(arr, start, mid-1) && isPostOrder(arr, mid, end-1);
	}
}

发表于 2020-12-22 10:34:19 回复(0)
#include<bits/stdc++.h>
using namespace std;
bool judge(int start,int end,vector<int>& v)
{
    if(start==end) return true;
    int i;
    // 找到第一个比根节点大的位置
    for(i=start;i<end;++i)
    {
        if(v[i]>v[end])
            break;
    }
    // 单支树
    if(i==start || i==end)
        return judge(start,end-1,v);
    // 否则,小于根值的结点在左侧,大于根的节点值须在右侧
    for(int j=i;j<end;++j)
    {
        if(v[j]<v[end])
            return false;
    }
    return judge(start,i-1,v) && judge(i,end-1,v);
}
int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i)
    {
        cin>>v[i];
    }
    cout<<( judge(0,n-1,v) ? "true" : "false");
    return 0;
}
发表于 2020-02-06 15:43:10 回复(0)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        System.out.println(isPostOrder(arr, 0, n-1));
		
	}
	
	
	private static boolean isPostOrder(int arr[],int start,int end) {
		if(start >=end) return true;
		
		int rootVal = arr[end];
		boolean flag = false;
		int mid = end;
		for(int i=start;i<end;i++) {
			if(!flag && arr[i]>rootVal) {
				mid = i;
				flag = true;
			}else if(flag && arr[i]<rootVal) {
				return false;
			}
		}
		
		return isPostOrder(arr, start, mid-1) && isPostOrder(arr, mid, end-1);
	}
}

发表于 2019-10-29 14:18:19 回复(0)