对称二叉树

LeetCode 101

问题描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

思路

递归

1. 如果树为空，则是轴对称的，直接返回 true。
2. 编写一个辅助函数 isSymmetricHelper，该函数接受两个节点作为参数，分别表示当前层级的左右节点。
3. 在 isSymmetricHelper中，进行以下判断：
   • 如果两个节点都为空，则返回 true。
   • 如果只有一个节点为空，或者两个节点的值不相等，则返回 false。
   • 否则，递归地判断左节点的左子树和右节点的右子树是否对称，并且左节点的右子树和右节点的左子树是否对称。
4. 最终返回 isSymmetricHelper(root->left, root->right)，表示从根节点开始的二叉树是否轴对称。

非递归

1. 首先检查根节点是否为空，若为空则返回 true。
2. 创建一个队列 q，并将根节点的左右子节点依次入队。
3. 每次从队列中取出两个节点，分别表示当前层级对称的左右节点。
4. 如果两个节点都为空，则继续下一次循环。
5. 如果其中一个节点为空，或者两个节点的值不相等，则返回 false。
6. 将左节点的左子节点与右节点的右子节点、左节点的右子节点与右节点的左子节点依次入队。
7. 循环直到队列为空，返回 true。

图解

1. 创建一个队列 q，并将根节点的左右子节点依次入队。

2. 当队列不为空时，将左右节点分别弹出队列。

3. 将左节点的左子节点与右节点的右子节点、左节点的右子节点与右节点的左子节点依次入队。

4. 队列不为空，将节点依次弹出队列。

此时，队列为空，返回 true。

参考代码

C++

递归

#include <iostream>

using namespace std;

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

// 辅助函数，判断以left和right为根节点的两棵树是否轴对称
bool isSymmetricHelper(TreeNode* left, TreeNode* right) {
    // 如果两个节点都为空，则对称
    if (!left && !right) {
        return true;
    }
    // 如果只有一个节点为空，或者两个节点的值不相等，则不对称
    if (!left || !right || left->val != right->val) {
        return false;
    }
    // 递归判断左节点的左子树和右节点的右子树，以及左节点的右子树和右节点的左子树是否对称
    return isSymmetricHelper(left->left, right->right) && isSymmetricHelper(left->right, right->left);
}

// 主函数，检查二叉树是否轴对称
bool isSymmetric(TreeNode* root) {
    if (!root) {
        return true; // 空树是对称的
    }
    return isSymmetricHelper(root->left, root->right);
}

// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr; // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1); // 创建左子树
    root->right = createTree(nodes, 2 * index + 2); // 创建右子树
    return root; // 返回当前节点
}

int main() {
    // 输入二叉树的先序遍历序列，-1表示空节点
    vector<int> nodes = {1, 2, 2, 3, 4, 4, 3};
    TreeNode* root = createTree(nodes, 0); // 创建二叉树
    cout << (isSymmetric(root) ? "true" : "false") << endl; // 检查是否轴对称

    return 0;
}

非递归

#include <iostream>
#include <queue>

using namespace std;

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return true; // 空树是对称的
        }

        queue<TreeNode*> q; // 辅助队列，用于层级遍历
        q.push(root->left); // 将根节点的左子节点入队
        q.push(root->right); // 将根节点的右子节点入队

        while (!q.empty()) {
            TreeNode* leftNode = q.front(); // 当前层级对称的左节点
            q.pop();
            TreeNode* rightNode = q.front(); // 当前层级对称的右节点
            q.pop();

            if (!leftNode && !rightNode) {
                continue; // 左右节点都为空，继续下一次循环
            }
            if (!leftNode || !rightNode || leftNode->val != rightNode->val) {
                return false; // 左右节点有一个为空，或者值不相等，返回 false
            }

            // 将左节点的左子节点与右节点的右子节点、左节点的右子节点与右节点的左子节点依次入队
            q.push(leftNode->left);
            q.push(rightNode->right);
            q.push(leftNode->right);
            q.push(rightNode->left);
        }

        return true; // 遍历完所有对称节点，返回 true
    }
};

// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
    if (index >= nodes.size() || nodes[index] == -1) {
        return nullptr; // 如果节点为空，则返回nullptr
    }
    TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
    root->left = createTree(nodes, 2 * index + 1); // 创建左子树
    root->right = createTree(nodes, 2 * index + 2); // 创建右子树
    return root; // 返回当前节点
}

int main() {
    vector<int> nodes = {1, 2, 2, 3, 4, 4, 3}; // 对称的二叉树的层序遍历序列
    TreeNode* root = createTree(nodes, 0); // 创建二叉树
    Solution solution;
    bool result = solution.isSymmetric(root); // 判断二叉树是否对称
    cout << (result ? "true" : "false") << endl; // 输出结果

    return 0;
}

Java

import java.util.LinkedList;
import java.util.Queue;

// 二叉树节点的定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true; // 空树是对称的
        }

        Queue<TreeNode> q = new LinkedList<>(); // 辅助队列，用于层级遍历
        q.offer(root.left); // 将根节点的左子节点入队
        q.offer(root.right); // 将根节点的右子节点入队

        while (!q.isEmpty()) {
            TreeNode leftNode = q.poll(); // 当前层级对称的左节点
            TreeNode rightNode = q.poll(); // 当前层级对称的右节点

            if (leftNode == null && rightNode == null) {
                continue; // 左右节点都为空，继续下一次循环
            }
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false; // 左右节点有一个为空，或者值不相等，返回 false
            }

            // 将左节点的左子节点与右节点的右子节点、左节点的右子节点与右节点的左子节点依次入队
            q.offer(leftNode.left);
            q.offer(rightNode.right);
            q.offer(leftNode.right);
            q.offer(rightNode.left);
        }

        return true; // 遍历完所有对称节点，返回 true
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nodes = {1, 2, 2, 3, 4, 4, 3}; // 对称的二叉树的层序遍历序列
        TreeNode root = createTree(nodes, 0); // 创建二叉树
        Solution solution = new Solution();
        boolean result = solution.isSymmetric(root); // 判断二叉树是否对称
        System.out.println(result ? "true" : "false"); // 输出结果
    }

    // 创建二叉树
    public static TreeNode createTree(int[] nodes, int index) {
        if (index >= nodes.length || nodes[index] == -1) {
            return null; // 如果节点为空，则返回null
        }
        TreeNode root = new TreeNode(nodes[index]); // 创建当前节点
        root.left = createTree(nodes, 2 * index + 1); // 创建左子树
        root.right = createTree(nodes, 2 * index + 2); // 创建右子树
        return root; // 返回当前节点
    }
}

Python

from collections import deque

# 二叉树节点的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True  # 空树是对称的

        q = deque()  # 辅助队列，用于层级遍历
        q.append(root.left)  # 将根节点的左子节点入队
        q.append(root.right)  # 将根节点的右子节点入队

        while q:
            left_node = q.popleft()  # 当前层级对称的左节点
            right_node = q.popleft()  # 当前层级对称的右节点

            if not left_node and not right_node:
                continue  # 左右节点都为空，继续下一次循环
            if not left_node or not right_node or left_node.val != right_node.val:
                return False  # 左右节点有一个为空，或者值不相等，返回 false

            # 将左节点的左子节点与右节点的右子节点、左节点的右子节点与右节点的左子节点依次入队
            q.append(left_node.left)
            q.append(right_node.right)
            q.append(left_node.right)
            q.append(right_node.left)

        return True  # 遍历完所有对称节点，返回 true

# 创建二叉树
def create_tree(nodes, index):
    if index >= len(nodes) or nodes[index] is None:
        return None  # 如果节点为空，则返回 None
    root = TreeNode(nodes[index])  # 创建当前节点
    root.left = create_tree(nodes, 2 * index + 1)  # 创建左子树
    root.right = create_tree(nodes, 2 * index + 2)  # 创建右子树
    return root  # 返回当前节点

# 测试代码
nodes = [1, 2, 2, 3, 4, 4, 3]  # 对称的二叉树的层序遍历序列
root = create_tree(nodes, 0)  # 创建二叉树
solution = Solution()
result = solution.isSymmetric(root)  # 判断二叉树是否对称
print("true" if result else "false")  # 输出结果