leetcode 94. Binary Tree Inorder Traversal(이차 트리의 중차 반복, 귀속법, 비귀속법)

제목 요구

두 갈래 나무를 정해서 중순으로 훑어보는 결과를 되돌려줍니다.주: 귀속과 교체 두 가지 방법을 시도해 보세요.
비슷한 문제 해답: leetcode 144.Binary Tree Preorder Traversal(두 갈래 나무의 앞 순서 반복, 귀속법, 비귀속법)

예제

/* Example */
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

문제 풀이 사고방식

무엇이 중서 역력입니까?중: 뿌리 노드가 나타나는 위치를 가리킨다. 간단한 나무 구조를 예로 들면 나무의 모든 노드를 훑어볼 때 왼쪽 아이를 먼저 훑어보고 중간에 뿌리 노드를 훑어보고 마지막에 오른쪽 아이를 훑어본다.(결과: 3-2-1).

      2
    /   \
   3     1

이런 식으로 미루어 보면 우리는 먼저 뿌리를 훑어보고 그 다음은 왼쪽 아이, 마지막은 오른쪽 아이라는 것을 알 수 있다.(결과: 2-3-1) 뒷차례는 왼쪽 아이를 먼저 훑어보고 가운데는 오른쪽 아이를 훑어보고 마지막은 뿌리 노드이다.(결과: 3-1-2)
어떻게 중서 역행을 실현합니까?1. 귀속 귀속 방법은 트리 문제를 해결하는 데 자주 사용하는 방법으로 이해하기 쉽다. 본 문제를 풀 때 우리는 위에서 말한 중서 역행 방법에 따라 다음과 같은 코드를 쓸 수 있다.

/*
 vector  inorder; //  。
*/
vector<int> inorderTraversal(TreeNode* root) {
        inorderTraversal(root->left); //  
        inorder.push_back(root->val); //  
        inorderTraversal(root->right); //  
        }

기본 코드 (c++)

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root !=NULL)
        {
        inorderTraversal(root->left);
        inorder.push_back(root->val);
        inorderTraversal(root->right);
        }
        return inorder;
    }
    
private:
    vector<int> inorder;
  }

2. 교체법(비귀속)은 귀속 실현 트리의 반복이 매우 간단하기 때문에 면접을 볼 때 면접관이 귀속으로 하지 못하게 하기 때문에 여기서 비귀속 실현 트리의 반복을 소개합니다.창고라는 데이터 구조를 빌려 실현해야 한다.
우리가 생각해 보자. 중서가 두루 돌아다니는 요점은 뿌리 노드가 중간에 나타나는 위치이다.
우리는 어떻게 창고의 특성을 이용하여 이 관계를 실현합니까?
step1. 두 갈래 나무(아래 그림)에 대해 우리가 먼저 해야 할 일은 뿌리부터 왼쪽 아이를 훑어보는 것이다. 잎 노드 4(왼쪽 아이가 없을 때까지).그동안 누비던 모든 노드가 창고에 들어갈 것이다.
현재 창고 안에는 2, 3, 4가 있다.창고 꼭대기 요소는 4입니다.

      2
    /   \                             |           |
   3     1                            |     4     | --->stack.top()
  /     / \                           |     3     | 
*4     5   6						  |     2     |
   										————————
     tree                                 stack

step2. 4라는 노드에 대해 정렬을 한다. 중서가 흐르는 순서에 따라 왼쪽 아이 노드를 먼저 정한다. 그러나 이때 왼쪽 아이 결점이 없기 때문에 우리는 뿌리 노드의 값, 즉 4를 되돌려야 한다.이때 당신은 현재 창고 꼭대기에 저장된 원소가 바로 우리가 찾는 것이므로 창고 밖으로 나가는 조작을 통해 원소의 창고 밖으로 나가고 다음 노드의 값을 저장하는 것을 발견할 수 있습니다.(창고의 창고 꼭대기 요소를 추출하여 조작해야 하기 때문에 이 순환의 조건 중 하나는 창고가 비어 있지 않도록 유지하는 것입니다!! 코드를 보고 이해할 수 있습니다)
step3. 훑어보는 순서에 따라 마지막으로 오른쪽 아이의 결점을 훑어보아야 한다. 우리는 현재의 바늘을 오른쪽 아이의 결점을 가리키기만 하면 된다.
시간 복잡도 O(n), 각 노드를 한 번씩 훑어보고 공간 복잡도 O(n)는 트리 구조를 저장해야 한다.

비귀속 기본 코드 – AC 0ms(c++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
vector<int> inorderTraversal(TreeNode* root) {
       TreeNode*p = root;
       stack<TreeNode*>s;
       vector<int>nodes;
       while(!s.empty()||p) //  ， 。
       {
           if(p)
           {
               s.push(p);
               p=p->left;
           }
           else
           {
              p = s.top();
              s.pop();
              nodes.push_back(p->val);
              p=p->right;
           }
       }  
        return nodes;
    }

총결산

비귀속 정렬을 실현할 때 우리는 창고의 특성을 이용하여 우리가 매우 효율적으로 임무를 완성할 수 있도록 돕는다. 주의해야 할 점은 다음과 같다.

순환 조건의 설정은 현재 노드와 창고의 비공성을 확보하는 것이 매우 중요하다. 그렇지 않으면 Runtime error가 발생할 가능성이 크다

창고의 조작을 명심하고push진입,pop출(먼저 top()을 가리킨다

원본 링크:https://leetcode.com/problems/binary-tree-inorder-traversal/