C++LeetCode 구현(100.같은 트 리 판단)

[LeetCode]100.동일 트 리 판단 동일 트 리
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input:     1         1
    / \       / \
2   3     2   3
        [1,2,3],   [1,2,3]
Output: true
Example 2:
Input:     1         1
/           \
2             2
[1,2],     [1,null,2]
Output: false
Example 3:
Input:     1         1
/ \       / \
2   1     1   2
[1,2,1],   [1,1,2]
Output: false
두 나무 가 동일 한 지 여 부 를 판단 하 는 것 과 두 나무의 대칭 여 부 를 판단 하 는 것 은 모두 같은 원리 이 며,깊이 를 이용 해 DFS 를 우선 검색 해 재 귀적 한다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

이 문 제 는 재 귀적 이지 않 은 해법 도 있다.이 진 트 리 의 네 가지 옮 겨 다 니 기(층 서,선서,중 서,후 서)는 모두 각자 의 교체 와 재 귀적 인 쓰기 가 있 기 때문이다.여기 서 우 리 는 먼저 선서 의 교체 기법 을 살 펴 보고 두 개의 수 를 동시에 옮 겨 다 니 는 것 과 같다.그 다음 에 모든 노드 를 비교 하면 그 사이 의 그 방법 을 참조 할 수 있다Binary Tree Preorder Traversal참조 코드 는 다음 과 같다.
해법 2:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st;
        st.push(p); st.push(q);
        while (!st.empty()) {
            p = st.top(); st.pop();
            q = st.top(); st.pop();
            if (!p && !q) continue;
            if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
            st.push(p->right); st.push(q->right);
            st.push(p->left); st.push(q->left);
        }
        return true;
    }
};

중간 순서 로 옮 겨 다 니 는 교체 쓰기 도 사용 할 수 있 습 니 다.  Binary Tree Inorder Traversal코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st;
        while (p || q || !st.empty()) {
            while (p || q) {
                if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
                st.push(p); st.push(q);
                p = p->left; q = q->left;
            }
            p = st.top(); st.pop();
            q = st.top(); st.pop();
            p = p->right; q = q->right;
        }
        return true;
    }
};

후 서 를 옮 겨 다 니 는 교체 표기 법 에 대해 서 는 하나의 스 택 으로 만 할 수 없 을 것 같 습 니 다.스 택 의 꼭대기 요 소 를 꺼 낸 후에 바로 제거 하지 않 기 때 문 입 니 다.이렇게 한 스 택 을 사용 하면 두 그루 의 나무 결점 의 위치 관계 가 어 지 러 워 지고 각자 의 스 택 을 사용 하면 됩 니 다.예전 의 그 방법 에 대응 합 니 다.  Binary Tree Postorder Traversal코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st1, st2;
        TreeNode *head1, *head2;
        while (p || q || !st1.empty() || !st2.empty()) {
            while (p || q) {
                if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
                st1.push(p); st2.push(q);
                p = p->left; q = q->left;
            }
            p = st1.top(); 
            q = st2.top(); 
            if ((!p->right || p->right == head1) && (!q->right || q->right == head2)) {
                st1.pop(); st2.pop();
                head1 = p; head2 = q;
                p = nullptr; q = nullptr;
            } else {
                p = p->right;
                q = q->right;
            }
        }
        return true;
    }
};

층 서 를 옮 겨 다 니 는 교체 기법 에 대해 사실은 먼저 옮 겨 다 니 는 교체 기법 과 매우 유사 하 다.단지 스 택 을 대열 로 바 꾸 었 을 뿐 예전 의 그 방법 에 대응 할 뿐이다.  Binary Tree Level Order Traversal코드 는 다음 과 같 습 니 다.
해법 5:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        que.push(p); que.push(q);
        while (!que.empty()) {
            p = que.front(); que.pop();
            q = que.front(); que.pop();
            if (!p && !q) continue;
            if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
            que.push(p->right); que.push(q->right);
            que.push(p->left); que.push(q->left);
        }
        return true;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/100  
유사 한 제목:
Binary Tree Preorder Traversal
Binary Tree Inorder Traversal
Binary Tree Postorder Traversal
Binary Tree Level Order Traversal
참고 자료:
https://leetcode.com/problems/same-tree/
https://leetcode.com/problems/same-tree/discuss/32684/My-non-recursive-method
https://leetcode.com/problems/same-tree/discuss/32687/Five-line-Java-solution-with-recursion
C++구현 LeetCode(100.같은 트 리 판단)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 판단 같은 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!