Leetcode101 判断二叉树是否对称

题目描述

答案：

/**
 * 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) {
      return check(root,root); //重点，同时传递了连个参数
    }

    public boolean check(TreeNode p,TreeNode q) {
        if (p == null && q == null) { //两个节点都为空，返回true
            return true;
        }
        /**
         * 代码执行到这里，已经排除了两个都为null的情况，剩下三种情况：
         * 1. p为null, q不是null，return false。
         * 2. p不是null,q 是null，return false。
         * 3. p不是null,q也不是null。这种情况要继续比较。
         */
        if (p == null || q == null) { //这行代码容易错写成: if(p != null || q != null){ return false; }
            return false;
        }
        //两个都不为空的情况
        /**
         1.值相等
         2.比较左侧左子树和右侧右子树的值是否相等
         3.比较左侧右子树和右侧左子树的值是否相等
         */
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

完整测试代码：

import java.util.ArrayList;
import java.util.List;

public class Leetcode101 {
    public static void main(String[] args) {
        Integer[] a = {1, 2, 2, 3, 4, 4, 3};

        //最终循环体执行的是节点，而不是整数值，所以要先把数组转为节点列表，然后遍历
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if (a[i] == null) {
                list.add(null);
                continue;
            }
            TreeNode t = new TreeNode(a[i]);
            list.add(t);
        }

        for (int i = 0; i < list.size(); i++) {
            //增加判空，因为可能只有左子树，或者只有右子树
            if (2 * i + 1 < list.size() && list.get(2 * i + 1) != null) {
                list.get(i).left = list.get(2 * i + 1);
            }

            if (2 * i + 2 < list.size() && list.get(2 * i + 2) != null) {
                list.get(i).right = list.get(2 * i + 2);
            }
        }

        printNode(list.get(0));
        System.out.println();
        System.out.println(isSymmetric(list.get(0)));
    }


    public static void printNode(TreeNode n) { //先序输出
        if (n != null) {
            System.out.print(" " + n.val);
            printNode(n.left);
            printNode(n.right);
        }
    }

    public static boolean isSymmetric(TreeNode root) {
        return check(root, root); //重点，同时传递了连个参数
    }

    public static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) { //两个节点都为空，返回true
            return true;
        }
        /**
         * 代码执行到这里，已经排除了两个都为null的情况，剩下三种情况：
         * 1. p为null, q不是null，return false。
         * 2. p不是null,q 是null，return false。
         * 3. p不是null,q也不是null。这种情况要继续比较。
         */
        if (p == null || q == null) { //这行代码容易错写成: if(p != null || q != null){ return false; }
            return false;
        }
        //两个都不为空的情况
        /**
         1.值相等
         2.比较左侧左子树和右侧右子树的值是否相等
         3.比较左侧右子树和右侧左子树的值是否相等
         */
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }



}