101.[Leetcode]Symmetric Tree

제목:

두 갈래 나무가 대칭인지 아닌지를 판단하다

나의 생각:

귀속
그러나 일반적인 그런 귀환이 아닌지, 그런 귀환은 생각해 낼 수 없다. 왜냐하면 서브 노드가 대칭인지 부 노드인지는 확실히 아무런 관계가 없다고 생각하기 때문이다.
나는 한 노드의 좌우 노드를 옮겨다니며 창고에 기록하고, 동시에 오른쪽 왼쪽 (순서가 상반됨) 을 옮겨다니며 창고에 기록한다
그 다음에 두 창고를 비교해 즉시노드가 비어 있으면 -1로 설정해야 하며, 더 이상 val이 나타나지 않는 값이 매우 중요하다.
주의: 한계 조건, 뿌리가 비어 있을 때true로 되돌아오기;

// ， ， 
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 
        if(root == NULL) return true;
        stack<int> vals_1,vals_2;
        push_val(root->left,vals_1,1);
        push_val(root->right,vals_2,0);
        while(!vals_1.empty()){
           if(vals_2.empty()) return false; //vals_1 ， vals_2 ， 
           if(vals_1.top() != vals_2.top()) return false; // ，false
           vals_1.pop();
           vals_2.pop();
        }
        if(!vals_2.empty()) return false; //  
        return true;
    }

    void push_val(TreeNode* node,stack<int> &vals,int direction){ // , node val 
        if(node == NULL) {
            vals.push(-1); // ， ， 
            return;
        }
        vals.push(node->val);
        if(direction == 1) {
            push_val(node->left,vals,1);
            push_val(node->right,vals,1);
        } else {
            push_val(node->right,vals,0);
            push_val(node->left,vals,0);
        }
    }
};

공식 귀환도 한탄할 만하다.
분석이 옳다. 두 개의 나무 거울은 단지 두 개의 원소일 뿐이다.이 두 개의 뿌리 노드는 같다.노드 1의 왼쪽 노드와 노드 2의 오른쪽 노드 거울, 노드 1의 오른쪽 노드와 노드 2의 왼쪽 노드 거울,

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
}

두 번째 방법은 당연히 순환이다. 두 갈래 나무의 순서, 중순서, 후순서가 어떻게 순환으로 실현되는지 이 링크에서 설명하는 것은 매우 명확하다. 복습해 보자.

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 
        if(root == NULL) return true; //root 
        if(root->left == NULL && root->right == NULL) return true; //root 
        if(!(root->left != NULL && root->right != NULL)) return false; //root 

        stack<TreeNode*> nodes; // 
        nodes.push(root->left);
        nodes.push(root->right);
        while(!nodes.empty()){
            //v
            TreeNode* node1 = nodes.top();
            nodes.pop();
            TreeNode* node2 = nodes.top();
            nodes.pop();

            if(node1->val != node2->val) return false; //judge

            // left,right
            if((node1->left == NULL && node2->right != NULL) || (node1->left != NULL && node2->right == NULL))
            return false;
            if(node1->left != NULL && node2->right != NULL) {
                nodes.push(node1->left);
                nodes.push(node2->right);
            }
            // right,left
            if((node2->left == NULL && node1->right != NULL) || (node2->left != NULL && node1->right == NULL))
            return false;
            if(node2->left != NULL && node1->right != NULL) {
                nodes.push(node2->left);
                nodes.push(node1->right);
            }
        }

        return true;
    }
};