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

一、题目

输入：root = [1,2,3,4,5,6]
输出：6

二、解法

一般的做法是用bfs或dfs遍历节点，时间和空间复杂度是O(n)。

要利用完全二叉树这个性质，首先求出树的层数level（root是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;
        int level=0;
        TreeNode node=root;
        while(node.left!=null){
            level++;
            node=node.left;
        }
        int low=1<>=1;
        }
        return node!=null;
    }
}