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

[编程题]根据后序数组重建搜索二叉树

热度指数：1993 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个有 n 个不重复整数的数组 arr，判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。

输入描述:

第一行一个整数 n，表示数组的长度。

第二行 n 个整数 arr_i。

输出描述:

如果是搜索二叉树后序遍历的结果则输出 "true"，否则输出 "false"。

示例1

输入

3
1 3 2

输出

true

备注:

算法知识视频讲解

Java

pein531

二叉搜索树后序遍历的最后一个节点为根节点，且左子树的节点值均小于根节点值，右子树的节点值均大于根节点值。对于某棵用数组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)

Java

闫岩_2020

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)

Java

小星教授

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)