129. 求根到叶子节点数字之和

题意：

解题思路：

思路：每个节点仅被遍历一遍，所以时间复杂度是 O(n)
1. 从根节点递归遍历整棵树，每进入下一个子树，将当前的sum*10再加上该树的val
2. 当遍历到叶节点时[左右子树为空]，将路径总数添加到sum中；

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    private $sum = 0;
    function sumNumbers($root) {
        $this->dfs($root, $root->val);
        return $this->sum;
    }
    function dfs($root, $curSum) {
        if ($root->left == null && $root->right == null) {
            $this->sum += $curSum;
            return;
        }
        if ($root->left != null) {
            $this->dfs($root->left, $curSum * 10 + $root->left->val);
        }
        if ($root->right != null) {
            $this->dfs($root->right, $curSum * 10 + $root->right->val);
        }
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var sum int
func sumNumbers(root *TreeNode) int {
    sum = 0
    if root != nil {
        dfs(root, root.Val)
    }
    return sum
}
func dfs(root *TreeNode, curSum int) {
    if root.Left == nil && root.Right == nil {
        sum += curSum;
        return
    }
    if root.Left != nil {
        dfs(root.Left, curSum * 10 + root.Left.Val) //子节点 乘以10
    }
    if root.Right != nil {
        dfs(root.Right, curSum * 10 + root.Right.Val)
    }
}