leetcode 101. 对称二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 101. 对称二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.2

leetcode 101. 对称二叉树

这道题要求我们判断一颗二叉树是否是对称的。我使用的是广度优先搜索的思想，通过队列将需要比较的节点依次入队和出队，进行对称性的判断。下面直接上代码：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty())
        {
            TreeNode* leftnode = que.front(); que.pop();
            TreeNode* rightnode = que.front(); que.pop();
            
            //左右两节点都是空节点 也属于对称
            if(leftnode==nullptr && rightnode==nullptr) continue;
            //一节点为空另一节点不为空或者两节点值不同 都属于不对称的情况
            if(leftnode==nullptr || rightnode==nullptr || leftnode->val!=rightnode->val) return false;

            que.push(leftnode->left);
            que.push(rightnode->right);
            que.push(leftnode->right);
            que.push(rightnode->left);
        }
        return true;
    }
};

每次入队入两个节点，并且分别是左右子树的，然后进行对称性的判断，若满足对称条件则将左节点的左孩子和右节点的右孩子先入队，再将左节点的右孩子和右节点的左孩子入队。

2023.10.20

二刷。java代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root.left);
        que.add(root.right);
        while(!que.isEmpty()){
            TreeNode leftNode = que.remove();
            TreeNode rightNode = que.remove();
            if(leftNode == null && rightNode == null) continue;
            if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
            que.add(leftNode.left);
            que.add(rightNode.right);
            que.add(leftNode.right);
            que.add(rightNode.left);
        }
        return true;
    }
}

java中的队列和cpp中的操作有些许不同，这里稍微总结一下：

Queue是java中实现队列的接口，它总共只有6个方法，我们一般只用其中3个就可以了。Queue最常见的实现类有LinkedList。 Queue的6个方法分类：文章来源地址https://www.toymoban.com/news/detail-514792.html

压入元素(添加)：add()、offer()
- 相同：未超出容量，从队尾压入元素，返回压入的那个元素。
- 区别：在超出容量时，add()方法会对抛出异常，offer()返回false。
弹出元素(删除)：remove()、poll()
- 相同：容量大于0的时候，删除并返回队头被删除的那个元素。
- 区别：在容量为0的时候，remove()会抛出异常，poll()返回false。
获取队头元素(不删除)：element()、peek()
- 相同：容量大于0的时候，都返回队头元素。但是不删除。
- 区别：容量为0的时候，element()会抛出异常，peek()返回null。