leetcode101：对称二叉树

题目链接

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
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
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 = 0;

// 辅助函数：创建二叉树
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)
        和递归使用的栈空间有关，这里递归层数不超过 n。
*/
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return dfs(root, root);
    }

    bool dfs(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr || p->val != q->val) return false;
        return dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

/*
    迭代实现，层序遍历
    
    时间复杂度：O(n)
    空间复杂度：O(n)
        使用一个队列来维护结点，每个结点最多进队一次，出队一次，
        队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
*/
class Solution_1 {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;

        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while (!que.empty()) {
            TreeNode* p = que.front(); que.pop();
            TreeNode* q = que.front(); que.pop();

            if (p == nullptr && q == nullptr) continue; // 结点为空时，下一轮退出
            if (p == nullptr || q == nullptr || p->val != q->val) return false;

            que.push(p->left); que.push(q->right);
            que.push(p->right); que.push(q->left);
        }
        
        return true;
    }
};

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

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

    // 验证是否为对称二叉树
    bool result = solution.isSymmetric(root);
    // 打印结果
    cout << "Is Symmetric: " << (result ? "true" : "false") << endl;

    // 释放内存
    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
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)
        从上到下每个节点仅被遍历一遍，
        所以时间复杂度是 O(n)。
    空间复杂度：O(n)
        和递归使用的栈空间有关，这里递归层数不超过 n，
        故渐进空间复杂度为 O(n)。
*/
// 递归方式判断对称二叉树
func isSymmetric(root *TreeNode) bool {
    if root == nil {
		return true
	}
    return check(root, root)
}

func check(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil || p.Val != q.Val {
        return false
    }
    return check(p.Left, q.Right) && check(p.Right, q.Left)
}

/*
    基本思路：迭代实现
        使用一个队列，将根节点的左右子节点成对放入队列，
        然后每次取出两对节点进行比较，
        若都相等，则将它们的相应子节点再次成对放入队列，直到队列为空。
    
    时间复杂度：O(n)
    空间复杂度：O(n)
        使用一个队列来维护节点，每个节点最多进队一次，出队一次，
        队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
*/
// 迭代方式判断对称二叉树
func isSymmetric_1(root *TreeNode) bool {
    if root == nil {
		return true
	}

    queue := []*TreeNode{root.Left, root.Right}
    for len(queue) > 0 {
        left := queue[0]
        right := queue[1]
        queue = queue[2:]

        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val!= right.Val {
            return false
        }
        queue = append(queue, left.Left, right.Right, left.Right, right.Left)
    }

    return true
}

func main() {
    // 测试用例
	testCases := []struct {
		values   []int
		expected bool
	}{
		{
			values:   []int{1,2,2,3,4,4,3},
			expected: true,
		},
		{
			values:   []int{1,2,2,-1,3,-1,3},
			expected: false,
		},
	}

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

        if result == tc.expected {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
        }
	}
}
#leetcode
leetcode101：对称二叉树
https://lcf163.github.io/2024/03/10/leetcode101：对称二叉树/
作者
乘风的小站
发布于
2024年3月10日
许可协议