java - 如何检查 BST 的结构是否对称

Question

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

public void traverse (Layer root){     

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

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

感谢您的帮助

Answer 1

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

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);
    }