对称的二叉树.md

题目描述

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

二叉树节点定义如下：

public class BinaryTreeNode {
    double value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

测试用例

• 功能测试（对称的二叉树；因结构而不对称的二叉树；结构对称但节点值不对称的二叉树）
• 特殊输入测试（二叉树的根节点为空指针；只有一个节点的二叉树；所有节点的值都相同的二叉树）

题目考点

• 考察应聘者对二叉树的理解。
• 考察应聘者的思维能力，应聘者可以通过画图把抽象问题形象化。

解题思路

采用递归

只要左子树的右子树 和 右子树的左子树相同 左子树的左子树 和 右子树的右子树相同即可

如果采用栈或者队列，请需要考虑所有节点的值都相同的二叉树这种特殊输入测试。

自己解题

没有理解对称的判断。

参考解题

/**
 * 对称的二叉树
 *
 * @Author rex
 * 2018/8/3
 */
public class Solution {
    /**
     * 理解完镜像
     * 递归解法
     * @param pRoot
     * @return
     */
    boolean isSymmetrical(BinaryTreeNode pRoot) {
        if (pRoot == null) {
            return false;
        }
        return isSymmetrical(pRoot.left, pRoot.right);
    }

    boolean isSymmetrical(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) {
        if (pRoot1 == null && pRoot2 == null) {
            return true;
        }
        if (pRoot1 == null || pRoot2 == null || pRoot1.value != pRoot2.value) {
            return false;
        }
        return isSymmetrical(pRoot1.left, pRoot2.right) && isSymmetrical(pRoot1.right, pRoot2.left);
    }
}