222. Count Complete Tree Nodes Medium

1/**
2 * [222] Count Complete Tree Nodes
3 *
4 * Given the root of a complete binary tree, return the number of the nodes in the tree.
5 * According to <a href="http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees" target="_blank">Wikipedia</a>, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.
6 * Design an algorithm that runs in less than <code data-stringify-type="code">O(n) time complexity.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/14/complete.jpg" style="width: 372px; height: 302px;" />
10 * Input: root = [1,2,3,4,5,6]
11 * Output: 6
12 * 
13 * Example 2:
14 * 
15 * Input: root = []
16 * Output: 0
17 * 
18 * Example 3:
19 * 
20 * Input: root = [1]
21 * Output: 1
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	The number of nodes in the tree is in the range [0, 5 * 10^4].
27 * 	0 <= Node.val <= 5 * 10^4
28 * 	The tree is guaranteed to be complete.
29 * 
30 */
31pub struct Solution {}
32use crate::util::tree::{TreeNode, to_tree};
33
34// problem: https://leetcode.com/problems/count-complete-tree-nodes/
35// discuss: https://leetcode.com/problems/count-complete-tree-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for a binary tree node.
40// #[derive(Debug, PartialEq, Eq)]
41// pub struct TreeNode {
42//   pub val: i32,
43//   pub left: Option<Rc<RefCell<TreeNode>>>,
44//   pub right: Option<Rc<RefCell<TreeNode>>>,
45// }
46// 
47// impl TreeNode {
48//   #[inline]
49//   pub fn new(val: i32) -> Self {
50//     TreeNode {
51//       val,
52//       left: None,
53//       right: None
54//     }
55//   }
56// }
57use std::rc::Rc;
58use std::cell::RefCell;
59impl Solution {
60    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_222() {
73    }
74}
75