我正在編寫一個返回二叉樹節點值的垂直順序遍歷的函數。(即,從上到下,逐列)。這是預期輸入和輸出的示例:Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5) 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2Output:[ [4], [9,5], [3,0,1], [8,2], [7]]我的函數按預期輸出所有內容,除了[8,2]——我得到的[2,8]是:[[4] [9 5] [3 0 1] [2 8] [7]]這是我的函數的樣子:func verticalOrder(root *TreeNode) [][]int { if root == nil { return [][]int{} } var ( hd int m map[int][]int vals [][]int min int max int traverse func(t *TreeNode, hd int, m map[int][]int) ) m = make(map[int][]int) min = 0 max = 0 traverse = func(t *TreeNode, hd int, m map[int][]int) { if t == nil { return } m[hd] = append(m[hd], t.Val) if max < hd { max = hd } if min > hd { min = hd } traverse(t.Left, hd-1, m) traverse(t.Right, hd+1, m) } traverse(root, hd, m) for i := min; i <= max; i++ { vals = append(vals, m[i]) } return vals}本質上,我使用散列映射來跟蹤具有相同水平距離的節點,并將它們附加到數組中。我想弄清楚的是我的輸出如何與9and 一起正常工作5而不與8and一起工作2?非常感謝任何反饋!
1 回答

ITMISS
TA貢獻1871條經驗 獲得超8個贊
我沒有任何關系append
。
您正在對二叉樹進行 DFS 遍歷,該順序稱為該樹的 DFS 順序。問題是樹的 DFS 順序不是從上到下。
您的代碼2
在 node 之前訪問 node 8
,因此代碼m[hd] = append(m[hd], t.Val)
代替. 沒有什么不一致的。[2 8]
[8 2]
要解決這個問題,您可以使用 BFS 來遍歷樹,或者,您可以將深度信息保存到其中m
并m[hd]
相應地對每個信息進行排序。
一般來說,BFS 是一個更好的主意,但排序很快就可以破解。
- 1 回答
- 0 關注
- 113 瀏覽
添加回答
舉報
0/150
提交
取消