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.
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.
Solution 1:
先看左右两路径的高度是否一样，如果一样，直接计算节点数目， 如果不一样，在递归。
先看左右两路径的高度是否一样，如果一样，直接计算节点数目， 如果不一样，在递归。
calculate height of right tree, if the same as height, go to right tree(append 1 to binary result), otherwise go to left tree (Append 0 to binary result)
No comments:
Post a Comment