剑指 Offer 28. 对称的二叉树

本是古典何须时尚 2022-12-09 02:47 114阅读 0赞

**题目：**  
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

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

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

**示例 1：**

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

**示例 2：**

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

**限制：**

0 <= 节点个数 <= 1000

题解：

/** * 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) { 
            if(root == null) { 
                return true;
            }
            //创建双端队列
            Deque<TreeNode> d = new LinkedList();
            //把左结点加入到首位置，把右结点加入到尾部
            d.addFirst(root.left);
            d.addLast(root.right);
            //到双端队列不为空时
            while(!d.isEmpty()) { 
                //取首结点
                TreeNode L = d.removeFirst();
                //取尾结点
                TreeNode R = d.removeLast();
                //当取出的结点的都为空时
                if(R == null && L == null) { 
                    continue;
                }
                //当取出的结点有一个为空，或值不相等时
                if(R == null || L == null || R.val != L.val) { 
                    return false;
                }
                //把左边的右子结点加入最头部
                d.addFirst(L.right);
                //把左边的左结点加入到最头部
                d.addFirst(L.left);
                //把右边的左子结点加入到最尾部
                d.addLast(R.left);
                //把右边的右子结点加入到最尾部
                d.addLast(R.right);
                
            }
            return true;
            
    
        }
    }

/** * 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) { 
            if(root == null) { 
                return true;
            }
            return helper(root.left,root.right);
    
        }
        //判断左右节点是否可以互换
        public boolean helper(TreeNode a,TreeNode b) { 
            //如果左节点为空，且右节点也为空
            if(a == null && b == null) return true;
            //左右节点节点至少有一个为空
            if(a == null || b == null) return false;
    
            return a.val == b.val && helper(a.left,b.right) && helper(a.right,b.left);
        }
    }