leetcode-101

题目

    1
   / \
  2   2
 / \ / \
3  4 4  3

    1
   / \
  2   2
   \   \
    3    3

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

1. 节点 p,q 的值相等（第一步即 root 节点自身比较，显然相等）

2. 节点 p 左孩子与 节点 q 右孩子相等

3. 节点 p 右孩子与 节点 q 左孩子相等

public boolean check(TreeNode p, TreeNode q) {}

1. 节点均为 null 时返回 true
此时该节点显然对称

if (p == null && q == null) {    return true;}

2. 节点仅有一个为 null 时返回 false
显然此时不对称

if (p == null || q == null) {   return false;}

3. 当前节点的值相等，且满足对称二叉树的 2，3 条性质

return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);

题解

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isSymmetric(TreeNode root) {        return check(root, root);    }    public boolean check(TreeNode p, TreeNode q) {        if (p == null && q == null) {            return true;        }        if (p == null || q == null) {            return false;        }        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);    }}

总结

迭代解法

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public boolean isSymmetric(TreeNode root) {        return check(root, root);    }    public boolean check(TreeNode u, TreeNode v) {        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(u);        queue.offer(v);        while(!queue.isEmpty()) {            u = queue.poll();            v = queue.poll();            if (u == null && v == null) {                continue;            }            if (u == null || v == null || u.val != v.val) {                return false;            }            queue.offer(u.left);            queue.offer(v.right);            queue.offer(u.right);            queue.offer(v.left);        }        return true;    }}