NC5 二叉树根节点到叶子节点的所有路径和_c++给定一个二叉树的根节点root,该树的节点值都在数字0-9之间,每一条从根节点到叶

描述

给定一个二叉树的根节点root，该树的节点值都在数字\ 0-9 0−9 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};
 
 
class Solution {
public:
	/**
	*
	* @param root TreeNode类
	* @return int整型
	*/
	int dfs(TreeNode* root, int num)
	{
		if (root == nullptr)//空结点直接返回0
			return 0;
 
		int sum = num * 10 + root->val;//当前路径值
		if (root->left==nullptr&&root->right==nullptr)//当前结点是叶子结点才返回路径值
			return sum;
 
		int leftSum = 0, rightSum = 0;
		if (root->left)
			leftSum = dfs(root->left, sum);
		if (root->right)
			rightSum = dfs(root->right, sum);
		return leftSum + rightSum;
	}
 
	int sumNumbers(TreeNode* root) {
		// write code here
		return dfs(root, 0);
	}
};