求根叶数字总和-蒲公英云

求根叶数字总和

问题描述：
给定一个只包含 0-9 数字的二叉树，每个根到叶的路径可以代表一个数字。
例如，从根到叶路径 1->2->3则代表数字 123。
查找所有根到叶数字的总和。
例如，

1
/ \
2 3
根到叶子路径 1->2 表示数字 12。
根到叶子路径 1->3 表示数字 13。
返回总和 = 12 + 13 = 25。

实现思路：
这是一个深度优先遍历，我想使用栈来实现。
1.使用三个栈，分别存放节点，路径和，该节点是否有两个孩子
2.遍历这颗树，若为叶子节点，则计算该叶子节点的数字并加到sum。
代码如下：

class Solution {
    public int sumNumbers(TreeNode root) {
        Stack<TreeNode> stackTree = new Stack<TreeNode>();// 存放节点
        Stack<Integer> num = new Stack<Integer>();// 存放数据
        Stack<Boolean> hasTwo = new Stack<Boolean>();// 存放数据
        TreeNode p = root;
        int sum = 0;
        while (p != null) {
            if (p.right == null && p.left == null) {
   //为叶子节点
                if (num.isEmpty()) {
   //数字栈为空，则节点的数据即为结果
                    sum += p.val;
                    break;
                } else {
   //否则根据数据栈顶元素来计算结果
                    sum = sum + num.peek() * 10 + p.val;
                    //将只有一个孩子的结点出栈全部
                    while (!hasTwo.isEmpty() && hasTwo.peek() == false) {
                        stackTree.pop();
                        num.pop();
                        hasTwo.pop();
                    }
                    //栈空则直接跳出
                    if (hasTwo.isEmpty()) {
                        break;
                    } else {
                       //否则，p指向节点栈顶元素的右孩子
                        p = stackTree.peek().right;
                        hasTwo.pop();
                        hasTwo.push(false);//并修改标识栈顶为false
                    }
                }
            } else {
                stackTree.push(p);//节点有孩子则入栈
                //数据栈入栈
                if (num.isEmpty()) {
                    num.push(p.val);
                } else {
                    num.push(num.peek() * 10 + p.val);
                }
                //两个孩子则标志栈入true，否则为false
                if (p.right != null && p.left != null) {
                    hasTwo.push(true);
                    p = p.left;//有两个孩子先访问左孩子
                } else {
                    hasTwo.push(false);
                    if (p.left != null) {
                        p = p.left;访问左孩子
                    } else {
                        p = p.right;//访问右孩子
                    }
                }
            }
            if (stackTree.isEmpty()) {
                break;//栈空则结束
            }
        }
        return sum;
    }
}