编程题 90 /123

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

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

例如根节点到叶子节点的一条路径是 $1\to 2\to 3$ ,那么这条路径就用 $\ 123$ 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：

这颗二叉树一共有两条路径，
根节点到叶子节点的路径 $1\to 2$ 用数字 $\ 12$ 代替
根节点到叶子节点的路径 $1\to 3$ 用数字 $\ 13$ 代替
所以答案为 $\ 12+13=25$

数据范围：节点数 $0 \le n \le 100$ ，保证结果在32位整型范围内

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n^2)$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

参考答案

先序遍历的思想(根左右)+数字求和(每一层都比上层和*10+当前根节点的值)

	public int sumNumbers(TreeNode root) {
		int sum = 0;
		if (root == null) {
			return sum;
		}
		return preorderSumNumbers(root, sum);
	}
	public int preorderSumNumbers(TreeNode root, int sum) {
		if (root == null)
			return 0;
		sum = sum * 10 + root.val;
		if (root.left == null && root.right == null) {
			return sum;
		}
		return preorderSumNumbers(root.left, sum) + preorderSumNumbers(root.right, sum);
	}

纠错收藏

查看讨论

1
...
85
86
87
88
89
90
91
92
93
94
95
...
123
跳转到

上一题下一题