FilesExpand file tree

 master

/

IsBSTPostOrder.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (31 loc) · 918 Bytes

 master

/

IsBSTPostOrder.java

Copy path

Top

File metadata and controls

• Code
• Blame

35 lines (31 loc) · 918 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

/**

* Is array post order of BST?

* post order: left, right, root

*/

public class IsBSTPostOrder {

public static void main(String[] args) {

int[] a = new int[]{0, 2, 1, 9, 12, 10, 6};

boolean postOrder = isBstPostOrder(a, 0, a.length - 1);

System.out.println(postOrder);

}

public static boolean isBstPostOrder(int[] a, int left, int right) {

if (left > right)

return false;

if ( right == left)

return true;

if(right - left == 1){

return true; //[left, root] or [root, right]

}

int i = left;

for (; i < right; i++) {

if (a[i] > a[right])

break;

}

int j = i;

for (; j < right; j++) {

if (a[j] < a[right])

return false;

}

return isBstPostOrder(a, left, i - 1) && isBstPostOrder(a, i, j-1);

}

}