FilesExpand file tree

 master

/

leetcode222.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

40 lines (37 loc) · 1.1 KB

 master

/

leetcode222.java

Top

File metadata and controls

• Code
• Blame

40 lines (37 loc) · 1.1 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

package leetcode.tree;

public class leetcode222 {

/*

* 常规解法

* */

public int countNodes(TreeNode root) {

if (root==null) return 0;

if (root.right==null && root.left==null) return 1;

return countNodes(root.right)+countNodes(root.left)+1;

}

/*

* 设，根节点的左子树高度和右节点高度为 left、right

* left==right 说明右子树有填充，左子树为满二叉树，递归右子树

* left==right 说明右子树无填充，左子树为完全二叉树，递归左子树

* */

public int countNodes2(TreeNode root) {

if (root==null) return 0;

int left=countLevel(root.left);

int right=countLevel(root.right);

if (left==right){

return countNodes2(root.right)+(1<<left);

}else {

return countNodes2(root.left)+(1<<right);

}

}

/*

非递归计算完全二叉树高度

* */

private int countLevel(TreeNode root){

int level=0;

while(root==null){

root=root.left;

level++;

}

return level;

}

}