未分類

Flatten Binary Tree to Linked List

DepthFirstSearch, Go, LeetCode, Tree

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example:

Given

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
提示 解題應用
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 flatten(root *TreeNode)  {
}

解答思路:

透過範例應該可以很明顯的發現二元樹的節點的順序是透過前序遍歷的方式來擺放，而且要將這棵二元樹轉成極端偏右的不平衡樹，既然此二元樹可以透過前序遍歷來取得節點順序，那麼只要先透過前序遍歷來將節點一一放入隊列之中，最後就可以透過隊列依序取出節點來構成極端偏右的不平衡樹。

程式碼解說:

因為會使用隊列來儲存節點順序，所以開頭先定義好隊列的結構

1
2
3
4
type QueneNode struct {
	Node *TreeNode
	Next *QueneNode
}

一開始先初始化隊列與極端偏右不平衡樹頭節節，以確保不論是在隊列還是建構二元樹上第一個節點都能與其它節點一樣有操作上的一致性，接著才將根節點與隊列頭節點帶入遞回函數之中，待遞回使所有節點都依序排入隊列之後，以兩個指標分別紀錄前一個節點的位置與當前節點的位置，不過因為最前面頭節點的位置是我們自行新增的，所以在遍歷隊列之前先將當前位置往後移再開始遍歷，每從隊列取出節點就先將左邊子節點的位置改為nil，接著才接到前一個節點右邊的位置，並再取出下一個隊列的節點之前，記得也要將前一個節點位置改為當前節點位置才再重覆先前的流程

1
2
3
4
5
6
7
8
9
10
11
12
func flatten(root *TreeNode) {
	header := &QueneNode{&TreeNode{}, nil}
	preOrderTravel(root, header)
	pre := header
	header = header.Next
	for header != nil {
		header.Node.Left = nil
		pre.Node.Right = header.Node
		pre = header
		header = header.Next
	}
}

前序遍歷的部分如果遍歷的節點不為空，就將該節點放入隊列之中並將隊列結尾的指標移到後頭，最後就是繼續前序遍歷分別往左右子樹再次進行遞回，並記得帶入每次回傳回來新的隊列結尾位置，待子樹都遍歷結束後，再向上回傳隊列結尾的指標，如果後續還有排序的節點才能繼續放入

1
2
3
4
5
6
7
8
9
func preOrderTravel(node *TreeNode, quene *QueneNode) *QueneNode {
	if node != nil {
		quene.Next = &QueneNode{node, nil}
		quene = quene.Next
		quene = preOrderTravel(node.Left, quene)
		quene = preOrderTravel(node.Right, quene)
	}
	return quene
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type QueneNode struct {
	Node *TreeNode
	Next *QueneNode
}
func flatten(root *TreeNode) {
	header := &QueneNode{&TreeNode{}, nil}
	preOrderTravel(root, header)
	pre := header
	header = header.Next
	for header != nil {
		header.Node.Left = nil
		pre.Node.Right = header.Node
		pre = header
		header = header.Next
	}
}
func preOrderTravel(node *TreeNode, quene *QueneNode) *QueneNode {
	if node != nil {
		quene.Next = &QueneNode{node, nil}
		quene = quene.Next
		quene = preOrderTravel(node.Left, quene)
		quene = preOrderTravel(node.Right, quene)
	}
	return quene
}

總結:

要將二元樹(節點的順序是透過前序遍歷的方式來擺放)轉成極端偏右的不平衡樹，只要先透過前序遍歷來將節點一一放入隊列之中，最後就可以透過隊列依序取出節點來構成極端偏右的不平衡樹。

分享到