数据结构之二叉树的遍历算法合集

判断一棵树是否是平衡二叉树

第一种:用一个整型,高1位代表true or false,低31位代表当前树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int isBalanced(TreeNode root) {
if (root == null) {
return merge(true, 0);
}
int left = isBalanced(root.left);
int right = isBalanced(root.right);
if (!getBoolean(left)) {
return left;
}

if (!getBoolean(right)) {
return right;
}

if (Math.abs(getValue(left) - getValue(right)) > 1) {
return merge(false, 0);
}

int height = Math.max(getValue(left), getValue(right)) + 1;

return merge(true, height);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int merge(boolean b, int value) {
int heightBit = 0x80000;
if (!b) {
heightBit = 0x70000;
}

int re = heightBit | value;
return re;
}

public boolean getBoolean(int arg) {
if ((arg & 0x80000) == 0x80000) {
return true;
} else {
return false;
}

}

public int getValue(int arg) {
int temp = arg & 0x7fff;
return temp;

}

第二种:直接用是否是-1代表是否是false,由于如果是-1就不需要高度了,所以这个也可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isBalanced3(TreeNode root) {
// write your code here
return maxDepth(root) != -1;
}

public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;

}
如果觉得有帮助就请我喝杯咖啡鼓励我继续创作吧^_^