222. Count Complete Tree Nodes

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public static int countNodes(TreeNode root){ if(root == null){ return 0; } int hl = getLeft(root)+1; int hr = getRight(root)+1; if(hl == hr){ int num = (2<<(hl-1))-1; return num; }else{ return countNodes(root.left)+countNodes(root.right)+1; } } public static int getRight(TreeNode root) { int cou = 0; TreeNode ptr = root; while(ptr.right != null){ cou++; ptr = ptr.right; } return cou; } public static int getLeft(TreeNode root) { int cou = 0; TreeNode ptr = root; while(ptr.left != null){ cou++; ptr = ptr.left; } return cou; }}

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int countNodes(TreeNode root) { if(root==null) return 0; return countNodes(root.left)+countNodes(root.right)+1; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。