你的位置:首页 > Java教程

[Java教程]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.

代码如下:(超时)

 1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *   int val; 5  *   TreeNode left; 6  *   TreeNode right; 7  *   TreeNode(int x) { val = x; } 8  * } 9 */10 public class Solution {11   public int countNodes(TreeNode root) {12     List<TreeNode> list=PreOrder(root);13     return list.size();14     15   }16   public List<TreeNode> PreOrder(TreeNode root){17     List<TreeNode> list=new ArrayList<>();18     if(root==null)19     return list;20     21     list.add(root);22     if(root.left!=null)23     list.addAll(PreOrder(root.left));24     if(root.right!=null)25     list.addAll(PreOrder(root.right));26     return list;27   }28 }