101. 对称二叉树

题目描述

链接: https://leetcode-cn.com/problems/symmetric-tree/submissions/
给定一个二叉树，检查它是否是镜像对称的。

题目分析

本题有两种解题方式:

• 递归方式
  如果一个树的左子树和右子树镜像对称, 那么这个树是对称的
  如果同时满足以下条件, 两个树互为镜像:
  1) 两个根节点具有相同的值
  2) 每个树的右子树都与另一个树的左子树镜像对称, 每个树的左子树都与另一个树的右子树镜像对称.
  
• 迭代方式
  利用栈来进行迭代.

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isMirror(TreeNode t, TreeNode s) {
        if (t != null && s != null) 
            return (t.val == s.val) && isMirror(t.left, s.right) && isMirror(t.right, s.left);
        else return t == null && s == null;
    }
    //递归方式
    public boolean isSymmetricRecursive(TreeNode root) {
        if (root == null) return true;
        // 检查左子树和右子树是否为镜面对称结构
        return isMirror(root.left, root.right);
    }
    // 迭代方式
    public boolean isSymmetricIterative(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left);
        stack.push(root.right);
        while (!stack.isEmpty()) {
            TreeNode s = stack.pop();
            TreeNode t = stack.pop();
            if (s == null && t != null || s != null && t == null)
                return false;
            if (s == null && t == null) continue;
            if (s.val != t.val) return false;
            stack.push(s.left);
            stack.push(t.right);
            stack.push(s.right);
            stack.push(t.left);
        }
        return true;
    }
    public boolean isSymmetric(TreeNode root) {
        //boolean result = isSymmetricIterative(root);
        boolean result = isSymmetricRecursive(root);
        return result;
    }
}