【改造先序遍历】222. 完全二叉树的节点个数

222. 完全二叉树的节点个数

解题思路-先序

• 直接改造先序遍历算法
• 针对一个节点 如果节点为空 那么直接返回0
• 其余交给递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        // 直接改造先序遍历算法

        // 针对一个节点做那些事情
        if(root == null){
            return 0;
        }

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

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

解题思路-降低时间复杂度

• 对于一颗完全二叉树 它的子树 一定有满二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        TreeNode l = root,r = root;
        // 记录左右子树的高度


        int hl = 0;
        int hr = 0;

        while(l != null){
            l  = l.left;
            hl++;
        }

        while(r != null){
            r = r.right;
            hr++;
        }

        // 如果左右子树高度相等  那么说明是一颗满二叉树   完全二叉树一定有子树是满二叉树
        // 该条件一定会出发
        if(hl == hr){
            return (int) Math.pow(2,hl) - 1;
        }


        // 如果左右二叉树的高度不一样  直接按照普通的二叉树进行计算 
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

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