对称的二叉树

题目 #

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

解题思路 #

  1. 定义一个对称的前序遍历,即root -> right -> left 与普通的前序遍历进行对比
  2. 相同则认为树是对称的
boolean isSymmetrical(TreeNode pRoot) {
    LinkedList<Integer> scanner = new LinkedList<>();
    LinkedList<Integer> symmetricalScanner = new LinkedList<>();

    preScanner(scanner, pRoot);
    symmetricalPreScanner(symmetricalScanner, pRoot);

    return scanner.equals(symmetricalScanner);
}

/**
 * 普通的前序遍历
 * @param res
 * @param root
 */
private void preScanner(LinkedList<Integer> res, TreeNode root) {
    if (root == null) {
        res.addLast(null);
        return;
    }

    res.addLast(root.val);

    preScanner(res, root.left);
    preScanner(res, root.right);
}

/**
 * 先右再左的前序遍历
 * @param res
 * @param root
 */
private void symmetricalPreScanner(LinkedList<Integer> res, TreeNode root) {
    if (root == null) {
        res.addLast(null);
        return;
    }

    res.addLast(root.val);

    symmetricalPreScanner(res, root.right);
    symmetricalPreScanner(res, root.left);
}