q101_对称二叉树

package 递归.q101_对称二叉树.f1;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
package 递归.q101_对称二叉树.f1;
import java.util.ArrayList;
import java.util.List;
/**
 * 层序遍历放入list对比 o(n*log(n))
 */
public class Solution {
    public boolean isSymmetric(List<TreeNode> nodes) {
        if (nodes.size() < 2) {
            return true;
        }
        int i = 0;
        int j = nodes.size() - 1;
        while (i < j) {
            if (nodes.get(i) == nodes.get(j)) {
                i++;
                j--;
            } else if (nodes.get(i) == null || nodes.get(j) == null || nodes.get(i).val != nodes.get(j).val) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        return true;
    }
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (list.size() != 0) {
            List<TreeNode> temp = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) != null) {
                    temp.add(list.get(i).left);
                    temp.add(list.get(i).right);
                }
            }
            if (!isSymmetric(temp)) {
                return false;
            }
            list = temp;
        }
        return true;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(2);
        root.left = t1;
        root.right = t2;
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        t1.left = t3;
        t1.right = t4;
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(3);
        t2.left = t5;
        t2.right = t6;
        System.out.println(new Solution().isSymmetric(root));
    }
}

package 递归.q101_对称二叉树.f2;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
package 递归.q101_对称二叉树.f2;
import java.util.LinkedList;
import java.util.Queue;
/**
 * 利用队列的层序遍历（广度优先搜索BFS）o(n)
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null) {
                return false;
            }
            if (t1.val != t2.val) {
                return false;
            }
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(2);
        root.left = t1;
        root.right = t2;
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        t1.left = t3;
        t1.right = t4;
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(3);
        t2.left = t5;
        t2.right = t6;
        System.out.println(new Solution().isSymmetric(root));
    }
}

package 递归.q101_对称二叉树.f3;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
package 递归.q101_对称二叉树.f3;
/**
 * 递归 o(n)（如果一个树的左子树与右子树镜像对称，那么这个树是对称的。根结点相同并且每个树的左子树和另一个树的右子树镜像对称的树是镜像对称的）
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        return (t1.val == t2.val)
                && isMirror(t1.right, t2.left)
                && isMirror(t1.left, t2.right);
    }
}