未分類

Sum Root to Leaf Numbers

DepthFirstSearch, Go, LeetCode, Tree

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example:

1
2
3
  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

提示 解題應用
DepthFirstSearch PreorderTravel

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
}

解答思路:

這題基本上就是一邊遍歷一邊將值做組合，最後發現到葉子節點的時候才一一將數值組合向上回傳做總合，至於數字要如何做組合也只是將之前的組合值乘上10之後再加上目前的節點值即可，待組合完畢後才將其帶入遞回函數繼續向下做前序遍歷。

程式碼解說:

一開始先判斷根節點是否為空，如果是則直接回傳0，不為空才將根節點與目前的數值組合帶入遞回函數之中

1
2
3
4
5
6
func sumNumbers(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return preOrderTravel(root, 0)
}

接著就是來處理前序遍歷的細節，因為要做數值組合再來等回傳才能做總合，所以先將之前的組合值乘上10之後再加上目前的節點值，之後判斷左右之節點是否存在，如果不存在表示已到達葉子節點回傳數值的組合，而如果任一邊不存在則繼續向另一邊做前序遍歷，最後如果兩邊子節點都存在，則兩邊都向下做前序遍歷，待兩邊的數值組合回來才做總合並向上回傳整個結果

1
2
3
4
5
6
7
8
9
10
11
func preOrderTravel(node *TreeNode, sum int) int {
	sum = sum*10 + node.Val
	if node.Left == nil && node.Right == nil {
		return sum
	} else if node.Left == nil {
		return preOrderTravel(node.Right, sum)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, sum)
	}
	return preOrderTravel(node.Left, sum) + preOrderTravel(node.Right, sum)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sumNumbers(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return preOrderTravel(root, 0)
}
func preOrderTravel(node *TreeNode, sum int) int {
	sum = sum*10 + node.Val
	if node.Left == nil && node.Right == nil {
		return sum
	} else if node.Left == nil {
		return preOrderTravel(node.Right, sum)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, sum)
	}
	return preOrderTravel(node.Left, sum) + preOrderTravel(node.Right, sum)
}

總結:

找出所有二元樹根到葉子的路徑並將路徑上的節點值做組合，最後回傳所有數值組合的總合，基本上就是一邊做前序遍歷一邊將值做組合，最後發現到葉子節點的時候才一一將數值組合向上回傳做總合，至於數字要如何做組合也只是將之前的組合值乘上10之後再加上目前的節點值即可。

分享到