leetcode 문제 풀이 사고 분석 (15) 99 - 105 문제

이 진 트 리 검색 트 리 의 두 노드 가 잘못 교환 되 었 습 니 다.그 구 조 를 바 꾸 지 않 고 이 나 무 를 회복 하 세 요.

이 문제 의 난점 은 잘못된 노드 를 어떻게 발견 하고 기록 한 후에 교환 하 느 냐 에 있다.일반적인 방법 은 세 단계 (1) 로 나 뉘 어 중간 순 서 를 통 해 정렬 수열 (2) 을 가 져 옵 니 다. 정렬 수열 에 문제 가 있 는 곳 (3) 을 다시 옮 겨 다 니 며 문제 가 발생 한 위 치 를 찾 고 값 을 교환 합 니 다. 그러나 실제 적 으로 옮 겨 다 니 는 과정 에서 문제 가 발생 한 곳 을 확인 할 수 있다 면 직접 교환 할 수 있 고 알고리즘 은 최적화 될 것 입 니 다.여 기 는 교체 와 재 귀 를 한 번 이상 옮 겨 다 닐 수 있 습 니 다. 그들 은 모두 O (H) 에 달 하 는 공간 으로 스 택 을 보존 해 야 합 니 다. 그 중에서 H 는 나무의 높이 를 말 합 니 다.Morris 알고리즘 은 두 번 옮 겨 다 니 는 방법 이지 만 상수 급 공간 을 옮 겨 다 니 는 방법 입 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void swap(TreeNode *a, TreeNode *b) 
    {
        int tmp = a->val;
        a->val = b->val;
        b->val = tmp;
    }

    void recoverTree(TreeNode *root) 
    {
        // predecessor is a Morris predecessor. 
        // In the 'loop' cases it could be equal to the node itself predecessor == root.
        // pred is a 'true' predecessor, 
        // the previous node in the inorder traversal.
        TreeNode *x = NULL, *y = NULL, *pred = NULL, *predecessor = NULL;

        while (root != NULL) {
        // If there is a left child
        // then compute the predecessor.
        // If there is no link predecessor.right = root --> set it.
        // If there is a link predecessor.right = root --> break it.
        if (root->left != NULL) {
            // Predecessor node is one step left 
            // and then right till you can.
            predecessor = root->left;
            while (predecessor->right != NULL && predecessor->right != root)
            predecessor = predecessor->right;

            // set link predecessor.right = root
            // and go to explore left subtree
            if (predecessor->right == NULL) {
            predecessor->right = root;
            root = root->left;
            }
            // break link predecessor.right = root
            // link is broken : time to change subtree and go right
            else {
            // check for the swapped nodes
            if (pred != NULL && root->val < pred->val) {
                y = root;
                if (x == NULL) x = pred;
            }
            pred = root;

            predecessor->right = NULL;
            root = root->right;
            }
        }
        // If there is no left child
        // then just go right.
        else {
            // check for the swapped nodes
            if (pred != NULL && root->val < pred->val) {
            y = root;
            if (x == NULL) x = pred;
            }
            pred = root;

            root = root->right;
        }
        }
        swap(x, y);
  }
};

같은 나무 에 두 개의 이 진 트 리 를 주 고 같은 지 확인 하 는 함 수 를 만 듭 니 다.만약 에 두 나무 가 구조 적 으로 같 고 노드 가 같은 값 을 가지 면 똑 같다 고 생각한다.

아주 간단 합 니 다. 옮 겨 다 니 며 비교 하면 됩 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL)
            return true;
        else if (p == NULL || q == NULL)
            return false;
            
        if (p->val != q->val)
            return false;
        if (p->left == NULL && q->left == NULL
            && p->right == NULL && q->right == NULL
            && p->val == q->val)
            return true;
        
        if (isSameTree(p->left, q->left) && 
            isSameTree(p->right, q->right))
            return true;
        else return false;
    }
};

대칭 이 진 트 리 에 이 진 트 리 를 주 고 거울 이 대칭 적 인지 확인 합 니 다.

이 문 제 는 재 귀 구 해 를 통 해 왼쪽 나무의 왼쪽 나무 와 오른쪽 나무의 오른쪽 나무, 그리고 왼쪽 나무의 오른쪽 나무 와 오른쪽 나무의 왼쪽 나 무 를 차례대로 판단 하면 된다.대기 열 이나 스 택 을 사용 할 수도 있 고 원리 가 같 습 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        else 
            return isSame(root->left, root->right);
    }

    bool isSame(TreeNode *lhs, TreeNode *rhs)
    {
        if (lhs == NULL && rhs == NULL)
            return true;
        else if (lhs == NULL || rhs == NULL)
            return false;

        if (lhs->val == rhs->val)
            return (isSame(lhs->left, rhs->right) && 
                isSame(lhs->right, rhs->left));
        else return false;
    }
};

이 진 트 리 의 층 차 는 이 진 트 리 를 옮 겨 다 니 며 층 차 를 따라 옮 겨 다 니 는 노드 값 을 되 돌려 줍 니 다.(즉, 한 층 한 층 왼쪽 에서 오른쪽으로 모든 노드 를 방문 하 는 것).

보통 한 개의 변 수 를 옮 겨 다 니 며 등급 을 기록 하면 되 고 그 다음 에 해당 하 는 등급 의 기록 을 기록 하면 됩 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> ret;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        search(root, 0);
        return ret;
    }

    void search(TreeNode *root, int height)
    {
        if (root == NULL)
            return;

        if(ret.size() == height)       
            ret.resize(height + 1);

        ret[height].push_back(root->val);
        height++;
        search(root->left, height);
        search(root->right, height);
    }
};

이 진 트 리 의 톱니 모양 층 차 는 이 진 트 리 를 옮 겨 다 니 며 노드 값 의 톱니 모양 층 차 를 되 돌려 줍 니 다.(즉, 왼쪽 에서 오른쪽으로, 오른쪽 에서 왼쪽으로 다음 층 을 옮 겨 다 니 는 것 을 유추 하여 층 과 층 사 이 를 교체 하여 진행 하 는 것 이다).

본 문제 와 위의 문 제 는 사실 별 차이 가 없 으 니, 한 단계 더 해서 이전 이나 뒤에서 판단 하면 된다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> ret;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        search(root, 0);
        return ret;
    }

    void search(TreeNode *root, int height)
    {
        if (root == NULL)
            return;

        if(ret.size() == height)       
            ret.resize(height + 1);
        if (height % 2 == 0)
            ret[height].push_back(root->val);
        else ret[height].insert(ret[height].begin(), root->val);
        height++;
        search(root->left, height);
        search(root->right, height);
    }   
};

이 진 트 리 의 최대 깊이

간단 한 문제 입 니 다. 크기 를 옮 겨 다 니 며 최대 치 를 기록 하면 됩 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int max = 0;
public:
    int maxDepth(TreeNode* root) {
        int height = 0;
        search(root, height);
        return max;
    }
    void search(TreeNode *root, int height)
    {
        if (root == NULL)
            return;
        else
        {
            height++;
            if (height > max)
                max = height;
            search(root->left, height);
            search(root->right, height);
        }
    }

};

이전 순서 와 중간 순서 가 서열 구조 이 진 트 리

본 문제 의 핵심 사상 은 앞의 순서 가 뿌리 노드 이 고 중간 순서 뿌리 노드 왼쪽 은 왼쪽 나무 이기 때문에 재 귀적 으로 찾 을 수 있다. 매번 에 앞 순서 로 뿌리 를 판단 하고 중간 순서 로 좌우 자 나 무 를 판단 한 다음 에 좌우 자 나 무 는 이 규칙 에 따라 계속 판단 하고 노드 가 없 을 때 까지 판단 할 수 있다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pos = 0;
        return buildTree(preorder, pos, inorder, 0, inorder.size() - 1);
    }

    TreeNode* buildTree(vector<int>& preorder, int& pos, vector<int>& inorder, int left, int right) 
    {
        if (pos >= preorder.size()) 
            return 0;

        int i = left;

        //              i
        for (; i <= right; ++i) 
        {
            if (inorder[i] == preorder[pos]) 
                break;
        }

        //         pos
        TreeNode* node = new TreeNode(preorder[pos]);

        //              
        if (left <= i - 1) 
            node->left = buildTree(preorder, ++pos, inorder, left, i - 1);  //    

        //             
        if (i + 1 <= right) 
            node->right = buildTree(preorder, ++pos, inorder, i + 1, right);  //    

        return node;
    }
};