未分類

Sum of Left Leaves

Go, LeetCode, Tree

Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

For Example:

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
提示 解題應用
Tree 前序遍歷

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 sumOfLeftLeaves(root *TreeNode) int {
}

解答思路:

非常容易的一題，基本上先寫出前序遍歷所有葉子節點的總合值之後，剩下的只要在多一個判斷來知道該”葉子”是否是右子節點，如果是就回傳0，否則就回傳節點原本的值，如此一來當”葉子”左右子節點都存在的時候，因為右子節點回傳值是0，總合相加的結果就會是只有”葉子”左子節點的值，之所以會強調葉子是因為若非葉子節點，不能直接將右子節點直接歸0，因為右邊可能還包含一顆子樹，所以最後判斷回傳值只能在確定為葉子節點的情況下做。

程式碼解說:

一開始先確認根節點是否為nil，如果是就回傳0，否則才開始前序遍歷

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

如果節點的左右子節點都為nil，就能確定該子節點為葉子節點，接著在判斷此葉子節點若為左側就回傳原本的值，如果是右則則回傳0，而如果該節點有一邊為nil另一邊不為nil，就繼續前序遍歷，並註明該子節點是否為左邊，如果是就將true做代入，否則右邊的子節點就代入false，而最後如果兩邊的子節點都存在，肯定不是葉子節點，直接將兩子節點值做總合回傳即可

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

完整程式碼:

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

總結:

要算出一樹某一側葉子節點的總合，首先先寫出全部葉子節點的總合，接著只要加入判斷是否為另一側的葉子節點，如果是的話在做回傳葉子節點值回傳值就回傳0，如此一來當左右葉子節點做總合時，就會是只有左葉子節點的值了。

分享到