未分類

Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

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

to

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

解答思路:

仔細觀查的話會發現只是子節點兩兩互換,而節點與節點間的子間點並不會互相影響,所以我們就可以先將左右子節點互換後再繼續往下遍歷,為前序遍歷的方式做處理就能很容易搞定了。

程式碼解說:

在前序遍歷的遞回中,只要記得先判斷該節點是否存在,就不需擔心其餘的處理會有問題,用一變數來暫存任一子節點的位置,將子節點兩兩互換後再對其遍歷,至於是否要有回傳值端看個人寫法,畢竟是傳址處理而又不需要比較回傳的結果

1
2
3
4
5
6
7
8
9
var tmp *TreeNode
if node != nil {
tmp = node.Left
node.Left = node.Right
node.Right = tmp
preOrderTravel(node.Left)
preOrderTravel(node.Right)
}
return node

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func invertTree(root *TreeNode) *TreeNode {
return preOrderTravel(root)
}
func preOrderTravel(node *TreeNode) *TreeNode {
var tmp *TreeNode
if node != nil {
tmp = node.Left
node.Left = node.Right
node.Right = tmp
preOrderTravel(node.Left)
preOrderTravel(node.Right)
}
return node
}

總結:

要將一樹節點的子節點左右兩兩位置互換,且節點與節點間的子間點並不會互相影響的話,藉由先將左右子節點互換後再往下遍歷(前序遍歷)即可。

分享到