Intuitively I use stack to solve this problem. Browsing the discussions makes me realize I can leverage this binary tree's property. However, how to prove this method work?
We know if the traversal is a valid binary tree's preorder traversal, then the number of leaves equals the number of nodes plus one. What's the mathematical proof that the later condition leads to the former statement?
How to prove #(leaves) equals #(nodes) + 1 method?


Think of it recursively.
Base case:
If you have one node in a binary tree, it has 1 node and 2 leaves.Recursive case:
for each new node you add to the binary tree, your new node replaces an old leave and add two new leaves, thus gives us 1 new node and 1 new leave.That extra 1 leave comes from the base case.