【数据结构-二叉树 八】【遍历求和】：求根到叶子节点数字之和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
         return dfsSum(root, 0);
    }
    private int dfsSum(TreeNode node, int preIndex) {
        // 1 递归终止，越过叶子节点，返回0;
        if (node == null) {
            return 0;
        }
        // 2 计算到当前节点的数值
        int curValue = preIndex * 10 + node.val;
        // 3 判断当前节点是否为叶子节点,到叶子节点则返回叶子节点值，非叶子节点的和为左右子节点的和
        if (node.left == null && node.right == null) {
            return curValue;
        } else {
            return dfsSum(node.left, curValue) + dfsSum(node.right, curValue);
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
       // 1 入参判断，如果root为空，返回0
        if (root == null) {
            return 0;
        }
        // 2 定义两个队列，一个为节点队列，一个为 节点值队列（用于存放当前节点为止的数字）
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> numQueue = new LinkedList<Integer>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        // 3 借助队列进行层次遍历
        int sum = 0;
        while (!nodeQueue.isEmpty()) {
            // 3-1 处理队头元素,获取节点和截止当前节点的数值
            TreeNode curNode = nodeQueue.poll();
            int curValue = numQueue.poll();
            if (curNode.left == null && curNode.right == null) {
                // 到了叶子节点则只剩下节点值，累加即可
                sum += curValue;
            } else {
                // 如果左子节点不为空，则将左子节点入队，并且更新左子节点的截止数值
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                    numQueue.offer(curValue * 10 + curNode.left.val);
                }
                // 如果右子节点不为空，则将右子节点入队，并且更新右子节点的截止数值
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                    numQueue.offer(curValue * 10 + curNode.right.val);
                }
            }
        }
        return sum ;
    }
}