FilesExpand file tree

 master

/

BalancedBinaryTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (64 loc) · 1.9 KB

 master

/

BalancedBinaryTree.java

Top

File metadata and controls

• Code
• Blame

75 lines (64 loc) · 1.9 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

65

66

67

68

69

70

71

72

73

74

75

package _55;

import structure.TreeNode;

// 平衡二叉树

// 输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中

// 任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

public class BalancedBinaryTree {

public static boolean isBalanced1(TreeNode root) {

if (root == null) {

return true;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

int diff = left - right;

if (diff > 1 || diff < -1) {

return false;

}

return isBalanced1(root.left) && isBalanced1(root.right);

}

public static boolean isBalanced2(TreeNode root) {

int[] depth = new int[]{0};

return isBalanced(root, depth);

}

public static boolean isBalanced(TreeNode root, int[] depth) {

if (root == null) {

depth[0] = 0;

return true;

}

int[] left = new int[]{0};

int[] right = new int[]{0};

if (isBalanced(root.left, left) && isBalanced(root.right, right)) {

int diff = left[0] - right[0];

if (diff <= 1 && diff >= -1) {

depth[0] = 1 + ((left[0] > right[0]) ? left[0] : right[0]);

return true;

}

}

return false;

}

public static int treeDepth(TreeNode root) {

if (root == null) {

return 0;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

return (left > right) ? left + 1 : right + 1;

}

public static void main(String[] args) {

// 1

// / \

// 2 3

// /\

// 4 5

// /

// 6

TreeNode root = new TreeNode(1);

root.left = new TreeNode(2);

root.right = new TreeNode(3);

root.left.left = new TreeNode(4);

root.left.right = new TreeNode(5);

root.left.right.left = new TreeNode(6);

System.out.println(isBalanced1(root));

System.out.println(isBalanced2(root));

}

}