美文网首页
剑指offer | 对称二叉树

剑指offer | 对称二叉树

作者: icebreakeros | 来源:发表于2019-08-04 16:12 被阅读0次

对称二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的
如果一棵二叉树和它的镜像一样,那么它是对称的

分析:
根据前序遍历,先遍历根结点,再遍历左结点,后遍历右结点,设计出一种镜像遍历方式:先遍历根结点,再遍历右结点,后遍历左结点,得到两个序列对应该完全相同

public class SymmetricalBinaryTree<Key extends Comparable<Key>> {

    private class Node {
        public Key key;
        public Node left, right;

        public Node(Key key) {
            this.key = key;
        }
    }

    public boolean isSymmetrical(Node node) {
        return isSymmetrical(node, node);
    }

    private boolean isSymmetrical(Node m, Node n) {
        if (m == null && n == null) {
            return true;
        }

        if (m == null || n == null) {
            return false;
        }

        if (m.key.compareTo(n.key) != 0) {
            return false;
        }
        return isSymmetrical(m.left, n.right) && isSymmetrical(m.right, n.left);
    }
}

相关文章

网友评论

      本文标题:剑指offer | 对称二叉树

      本文链接:https://www.haomeiwen.com/subject/qdjydctx.html