leetcode226：翻转二叉树

题目链接

leetcode

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

C++ 代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

	二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题可以同时使用这两种。
	如何翻转二叉树？把二叉树上每个结点的左右子结点都交换。

    时间复杂度：O(N)
        其中 N 为二叉树结点的数目。
        遍历二叉树中的每一个结点，对每个结点而言，在常数时间内交换其两棵子树。
    空间复杂度：O(N)
        由递归栈的深度决定，它等于当前结点在二叉树中的高度。
        在平均情况下，二叉树的高度与结点个数为对数关系，即 O(logN)。
        在最坏情况下，二叉树形成链状，空间复杂度为 O(N)。
	
	参考链接：
        https://labuladong.online/algo/data-structure/binary-tree-part1/
*/
// 思路：遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        traverse(root);
        return root;
    }

    void traverse(TreeNode* root) {
        if (root == nullptr) return;

        // 该结点交换左右子结点
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        // 遍历左右子树的结点
        traverse(root->left);
        traverse(root->right);
    }
};
// 思路：分解问题
class Solution_1 {
public:
    // 函数定义：以 root 为根结点的二叉树翻转，返回翻转后二叉树的根结点
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        // 根据函数定义，递归地翻转左右子树
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        // 交换左右子结点
        root->left = right;
        root->right = left;

        return root;
    }
};

/*
    迭代实现

    时间复杂度：O(N)
        其中 N 为二叉树结点的数目。
    空间复杂度：O(N)
*/
class Solution_2 {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top(); stk.pop();
            // 该结点交换左右子结点
            TreeNode* temp = node->left;
            node->left = node->right;
            node->right = temp;
            // 遍历左右子树的结点
            if (node->left != nullptr) stk.push(node->left);
            if (node->right != nullptr) stk.push(node->right);
        }

        return root;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {4, 2, 7, 1, 3, 6, 9};

    // 创建二叉树
    TreeNode* root = createTree(nums);

    // 翻转二叉树
    root = solution.invertTree(root);
    // 打印结果
    levelOrderTraversal(root);

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
package main

import "fmt"

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}


// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：递归实现
        从根节点开始，对于每个节点，先交换它的左右子树，
        然后递归地对其左右子树执行相同的交换操作，直到遍历完整个二叉树。

    时间复杂度：O(N)，
        其中 N 为二叉树节点的数目。
        遍历二叉树中的每一个节点，对每个节点而言，在常数时间内交换其两棵子树。
    空间复杂度：O(N)。
        空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。
        在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。
        在最坏情况下，二叉树形成链状，空间复杂度为 O(N)。
*/
// 递归方式翻转二叉树
func invertTree_0(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // 交换左右子节点
    root.Left, root.Right = root.Right, root.Left
    // 递归处理左右子树
    invertTree(root.Left)
    invertTree(root.Right)
    
    return root
}

/*
    基本思路：迭代实现
        使用一个栈来辅助。
        将根节点入栈，然后在循环中，取出栈顶节点，交换其左右子树，
        并将其非空的左右子节点入栈，重复这个过程，直到栈为空。
        
    时间复杂度：O(N)，
        其中 N 为二叉树节点的数目。
        遍历二叉树中的每一个节点，对每个节点而言，在常数时间内交换其两棵子树。
    空间复杂度：O(N)。
        空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。
        在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。
        在最坏情况下，二叉树形成链状，空间复杂度为 O(N)。
*/
// 迭代方式翻转二叉树
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            // 交换左右子树
			node.Left, node.Right = node.Right, node.Left
            // 将非空子树压入栈
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
        }
    }

    return root
}

func main() {
    // 测试用例
	testCases := []struct {
		values   []int
		expected []int
	}{
		{
			values:   []int{4,2,7,1,3,6,9},
			expected: []int{4,7,2,9,6,3,1},
		},
		{
			values:   []int{2,1,3},
			expected: []int{2,3,1},
		},
		{
			values:   []int{},
			expected: []int{},
		},
	}

	for i, tc := range testCases {
		root := createTree(tc.values)
		fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
		result := invertTree(root)
		resultStr := printTree(result)
		expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}
#leetcode
leetcode226：翻转二叉树
https://lcf163.github.io/2024/04/27/leetcode226：翻转二叉树/
作者
乘风的小站
发布于
2024年4月27日
许可协议