FilesExpand file tree

 master

/

BalancedBinaryTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

72 lines (58 loc) · 2.02 KB

 master

/

BalancedBinaryTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

72 lines (58 loc) · 2.02 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

/**

* Given a binary tree, determine if it is height-balanced.

* For this problem, a height-balanced binary tree is defined as a binary tree

* in which the depth of the two subtrees of every node never differ by more than 1.

*

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*

*

* =================================

* 1/13/2013 update:

* The previous method is O(n^2). A better O(n) solution is provided below.

*/

package com.congli.leetcode;

public class BalancedBinaryTree {

public boolean isBalanced(TreeNode root) {

return isBalancedHelper(root, 0);

}

private boolean isBalancedHelper(TreeNode root, int currentHeight)

{

if(root == null) return true;

int leftHeight = getHeight(root.left, currentHeight);

int rightHeight = getHeight(root.right, currentHeight);

if(leftHeight - rightHeight <= 1 && leftHeight - rightHeight >= -1)

{

return isBalancedHelper(root.left, currentHeight+1) && isBalancedHelper(root.right, currentHeight+1);

}

else

{

return false;

}

}

private int getHeight(TreeNode node, int height)

{

if(node == null) return height;

return Math.max(getHeight(node.left, height+1), getHeight(node.right, height+1));

}

////////////////////////////////////////////////////

////////////////////////////////////////////////////

public boolean isBalancedONTimeComplexity(TreeNode root) {

if(root == null) return true;

return helper(root)!= -1;

}

private int helper(TreeNode root)

{

if(root == null) return 0;

int leftHeight = helper(root.left);

int rightHeight = helper(root.right);

if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1)

return Math.max(leftHeight, rightHeight)+1;

return -1;

}

}