求根叶数字总和

阳光穿透心脏的1/2处 2021-09-26 15:08 277阅读 0赞

**问题描述**：  
给定一个只包含 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;
        }
    }