FilesExpand file tree

master

/

LeetCode98.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (57 loc) · 1.58 KB

master

/

LeetCode98.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (57 loc) · 1.58 KB

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

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* Description:

*

* @author elijahliu

* @Note Talk is cheap,just show me ur code.- -!

* ProjectName:EAlgorithm

* PackageName: tree

* Date: 2020/8/16 15:50

*/

public class LeetCode98 {

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

List<TreeNode> inOrder = new LinkedList<>();

public boolean isValidBST(TreeNode root) {

inOrder(root);

for (int i = 1; i < inOrder.size(); i++) {

if (inOrder.get(i).val <= inOrder.get(i - 1).val) {

return false;

}

}

return true;

}

// 方法1 利用二叉平衡术中序遍历之后是递增数组的特性，来判断是不是合法二叉树

void inOrder(TreeNode root) {

if (root == null) {

return;

}

inOrder(root.left);

inOrder.add(root);

inOrder(root.right);

}

// 方法二 同方法一类似 但是不需要存储整个数组，只需要记录前一个遍历的数，并且判断是不是小于后一个数即可

TreeNode preNode = null;

boolean inOrder2(TreeNode root){

if (root == null) {

return true;

}

//如果遍历左子树 不为平衡 则直接返回false

if (!inOrder2(root.left)) {

return false;

}

if (preNode != null && root.val <= preNode.val) {

return false;

}

preNode = root;

return inOrder2(root.right);

}

}