二叉树--自对称判断

今天学习的算法是判断二叉树是否自对称。

题目介绍

对称二叉树的特点是将跟节点的左右子树翻转后，树与原来保持完全一致。

先分别看下对称和非对称树吧：

对称链表-题目.png

实现思路

还是继续沿用递归的思想来解题吧，先看下实现思路图：

二叉树-对称二叉树解题.png

先直观的从图中来分析下解题的思路：

第一步：从根节点的左右子节点开始，先比较左节点和右节点是否相等，不相等则返回false，相等则进行下一步。

第二步：取出左节点的右子节点与右节点的左子节点重复第一步，同时取左节点的左子节点与右节点的右子节点进行第一步。只有上面两个同时为true才可进行下一步，否则返回false。

第三步：当比较的两个节点相等或者同时为null则当此递归比较返回true，否则返回false。

老规矩，我们找到递归实现的最重要的两点：
1、找到递归公式：F（left，right）= F（left.right，right.left）&& F（left.left，right.right）
2、找到终止条件：函数输入两个节点同时为Null，或者相等则返回true，否则返回false。

实现代码

public class SolutionSymmetricTree {

    public boolean isSymmetric(TreeNode root) {
        if (null == root) {
            return true;
        }
        return checkSymmetric(root.left, root.right);
    }


    public boolean checkSymmetric(TreeNode lRoot, TreeNode rRoot) {
        if ((lRoot == null && rRoot != null) || (lRoot != null && rRoot == null)) {
            return false;
        }
        if (lRoot == null && rRoot == null) {
            return true;
        } else if (lRoot != null && rRoot != null) {
            return (lRoot.val == rRoot.val) && checkSymmetric(lRoot.left, rRoot.right) && checkSymmetric(lRoot.right, rRoot.left);

        } else {
            return false;
        }
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms