Условие задачи
Инвертировать заданное бинарное дерево.
пример 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
|
Решение
Обход дерева в глубину
Собственно идея простоя – обходим дерево в глубину и меняем детей местами.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
if root.Left == nil && root.Right == nil {
return root
}
root.Right, root.Left = invertTree(root.Left), invertTree(root.Right)
return root
}
|