2

我正在编写一个程序，我需要知道 BST 的结构是否对称

public void traverse (Layer root){     

     if (root.leftChild != null){ 
         traverse (root.leftChild);           
     }
     if (root.rightChild != null){
         traverse (root.rightChild);
     }

我有遍历代码，但我不知道如何检查它是否是对称的

谢谢您的帮助

4

2 回答 2

2

我在学校里学会了如何做到这一点，这就是我所做的。我是从一个我不记得的网站上学到的，但我保留了其中的评论。

boolean isMirror(Node node1, Node node2) 
    {
        // if both trees are empty, then they are mirror image
        if (node1 == null && node2 == null)
            return true;

        // For two trees to be mirror images, the following three
        // conditions must be true
        // 1 - Their root node's key must be same
        // 2 - left subtree of left tree and right subtree
        //      of right tree have to be mirror images
        // 3 - right subtree of left tree and left subtree
        //      of right tree have to be mirror images
        if (node1 != null && node2 != null && node1.key == node2.key)
            return (isMirror(node1.left, node2.right)
                    && isMirror(node1.right, node2.left));

        // if neither of the above conditions is true then
        // root1 and root2 are mirror images
        return false;
    }
boolean isSymmetric(Node node) 
    {
        // check if tree is mirror of itself
        return isMirror(node, node);
    }
于 2017-03-28T00:43:11.940 回答
0 
public boolean isSymmetric(Layer root) {
    return root == null || isSymmetric(root.left, root.right);
}

public boolean isSymmetric(Layer left, Layer right) {
    if (left == null && right == null) return true;
    return left != null && right != null && left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}

我想你的意思是树是对称的，如果它是它自己的“镜子”

于 2017-03-28T00:42:50.520 回答