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
|
Default:
1 2 3 4 5 6 7 8 9 10 11
| 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 }
|
總結:
要將一樹節點的子節點左右兩兩位置互換,且節點與節點間的子間點並不會互相影響的話,藉由先將左右子節點互換後再往下遍歷(前序遍歷)即可。