未分類

Binary Tree Right Side View

BreadthFirstSearch, DepthFirstSearch, Go, LeetCode, Tree

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:

Given the following binary tree,

1
2
3
4
5
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

提示 解題應用
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 rightSideView(root *TreeNode) []int {
}

解答思路:

題目主要的意思就是要輸出每層最右側的節點，所以可以用廣度優先搜尋的方式將每層的最後一個節點給放入結果之中，或者是像這次的解法一樣採用前序遍歷的方式，每次再往下遍歷之前先檢查該節點右側是否有子節點存在，如果存在且該層尚未有節點放入結果之中(結果陣列的長度小於目前樹的深度)就將右側子節點值放入，而如果右側子節點不存在但左側存在，且該層一樣尚未有節點放入就將左側子節點值放入，最後待操作完畢要向下遞回遍歷時，記得要先遍歷完右子樹才遍歷左子樹(因為是以輸出最右側的節點為主)。

程式碼解說:

因為對於根節點來說不屬於左右兩側，所以為了確保操作上的一致性，就自行製做頭節點將根節點接於頭節點的右側並帶入前序遍歷的函數之中，其中第一個參數是遍歷的節點，第二個則是目前該節點在整個二元樹的深度，第三個才是目前已放入結果陣列的值

1
2
3
4
func rightSideView(root *TreeNode) []int {
	head := &TreeNode{0, nil, root}
	return preorderTravel(head, 0, []int{})
}

再來是前序遍歷函數的細節，一開始先檢查目前遍歷的節點是否存在，如果不存在則回傳整個結果陣列，而如果存在就再檢查該節點右側子節點是否一樣存在，且該層尚未有節點放入結果之中(結果陣列的長度小於目前樹的深度)就將右側子節點值放入，而如果右側子節點不存在但左側存在，且該層一樣尚未有節點放入就將左側子節點值放入，待操作完畢要向下遞回遍歷時，記得要先遍歷完右子樹才遍歷左子樹(因為是以輸出最右側的節點為主)，最後兩側子樹都遍歷結束後才向上回傳整個結果陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func preorderTravel(node *TreeNode, depth int, cur []int) []int {
	if node == nil {
		return cur
	}
	if node.Right != nil && len(cur) < depth+1 {
		cur = append(cur, node.Right.Val)
	}
	if node.Left != nil && len(cur) < depth+1 {
		cur = append(cur, node.Left.Val)
	}
	cur = preorderTravel(node.Right, depth+1, cur)
	cur = preorderTravel(node.Left, depth+1, cur)
	return cur
}

完整程式碼:

1
2
3
4
func rightSideView(root *TreeNode) []int {
	head := &TreeNode{0, nil, root}
	return preorderTravel(head, 0, []int{})
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func preorderTravel(node *TreeNode, depth int, cur []int) []int {
	if node == nil {
		return cur
	}
	if node.Right != nil && len(cur) < depth+1 {
		cur = append(cur, node.Right.Val)
	}
	if node.Left != nil && len(cur) < depth+1 {
		cur = append(cur, node.Left.Val)
	}
	cur = preorderTravel(node.Right, depth+1, cur)
	cur = preorderTravel(node.Left, depth+1, cur)
	return cur
}

總結:

如果要輸出二元樹中每層最右側的節點，可以用廣度優先搜尋的方式將每層的最後一個節點給放入結果之中，或者採用前序遍歷的方式每次再往下遍歷之前先檢查該節點右側是否有子節點存在，如果存在且該層尚未有節點放入結果之中(結果陣列的長度小於目前樹的深度)就將右側子節點值放入，而如果右側子節點不存在但左側存在，且該層一樣尚未有節點放入就將左側子節點值放入，最後待操作完畢要向下遞回遍歷時，記得要先遍歷完右子樹才遍歷左子樹(因為是以輸出最右側的節點為主)。

分享到