《剑指offer》对称的二叉树-ag真人游戏

题目描述：

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

解题思路：

  我们通常有三种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这三种遍历算法中，都是先遍历左子结点再遍历右子结点。以前序遍历为例，我们可以定义一个遍历算法，先遍历右子结点再遍历左子结点，暂且称其为前序遍历的对称遍历。

遍历第一棵树，前序遍历的遍历序列为{8,6,5,7,6,7,5}，其对称遍历的遍历序列为{8,6,5,7,6,7,5}。

遍历第二颗树，前序遍历的遍历序列为{8,6,5,7,9,7,5}，其对称遍历的遍历序列为{8,9,5,7,6,7,5}。

可以看到，使用此方法可以区分前两棵树，第一棵树为对称树，第二颗树不是对称树。但是当使用此方法，你会发现第三颗树的前序遍历和对称前序遍历的遍历序列是一样的。

怎么区分第三颗树呢？解决办法就是我们也要考虑null指针。此时，前序遍历的遍历序列{7,7,7,null,null,7,null,null,7,7,nll,null,null}，其对称遍历的遍历序列为{7,7,null,7,null,null,7,7,null,null,7,null,null}。因为两种遍历的序列不同，因此这棵树不是对称树。

代码实现(c )

/*
struct treenode {
    int val;
    struct treenode *left;
    struct treenode *right;
    treenode(int x) :
            val(x), left(null), right(null) {
    }
};
*/
class solution {
public:
    bool issymmetrical(treenode* proot)
    {
        if(proot == null){
            return true;
        }
        return issymmetriacalcor(proot, proot);
    }
private:
    bool issymmetriacalcor(treenode* proot1, treenode* proot2){
        if(proot1 == null && proot2 == null){
            return true;
        }
        if(proot1 == null || proot2 == null){
            return false;
        }
        if(proot1->val != proot2->val){
            return false;
        }
        return issymmetriacalcor(proot1->left, proot2->right) && issymmetriacalcor(proot1->right, proot2->left);
    }
};

代码实现(java)

public class treenode {
    int val = 0;
    treenode left = null;
    treenode right = null;
    public treenode(int val) {
        this.val = val;
    }
}
public class solution {
    boolean issymmetrical(treenode proot) {
        return issymmctrical(proot, proot);
    }
    public boolean issymmctrical(treenode root1, treenode root2) {
        if(root1 == null && root2 == null) {
            return true;
        }
        if(root1 == null || root2 == null) {
            return false;
        }
        if(root1.val != root2.val) {
            return false;
        }
        return issymmctrical(root1.left, root2.right) && issymmctrical(root1.right, root2.left);
    }
}

代码实现(python)

tree(self, left, right):
        if not left and not right:
            return true
        if not left or not right:
            return false
        if left.val == right.val:
            return self.recursivetree(left.left, right.right) and self.recursivetree(left.right, right.left)
        return false
if __name__=='__main__':
    a1 = treenode(1)
    a2 = treenode(2)
    a3 = treenode(2)
    a4 = treenode(3)
    a5 = treenode(4)
    a6 = treenode(4)
    a7 = treenode(3)
    a1.left=a2
    a1.right=a3
    a2.left=a4
    a2.right=a5
    a3.left=a6
    a3.right=a7
    solution = solution()
    ans=solution.issymmetrical(a1)
    print(ans)