LeetCode 94 Binary Tree Inorder Traversal (이 진 트 리 의 순서)

1840 단어 데이터 구조
Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree  [1,null,2,3] ,
   1
    \
     2
    /
   3

return  [1,3,2] .
Note: Recursive solution is trivial, could you do it iteratively?
제목: 두 갈래 트 리 에 순서대로 옮 겨 다 니 는 결 과 를 출력 합 니 다.
문제 풀이 방향: 이 진 트 리 에서 순서대로 옮 겨 다 니 는 순 서 는 먼저 왼쪽 트 리 를 옮 겨 다 니 고 그 다음 에 뿌리 노드 를 옮 겨 다 니 며 마지막 으로 오른쪽 트 리 를 옮 겨 다 니 는 것 입 니 다.제목 은 재 귀적 으로 옮 겨 다 니 는 표기 법 이 너무 흔 하 다 고 하 니, 우 리 는 재 귀적 이지 않 은 것 을 쓴다.중간 순서 로 옮 겨 다 니 는 순서에 따라 우 리 는 이렇게 처리 할 수 있다.
    임의의 노드 N 에 대해,
    1. N 의 왼쪽 아이 가 비어 있 지 않 으 면 N 을 스 택 에 넣 고 N 의 왼쪽 아 이 를 N 으로 설정 한 다음 N 을 동일 하 게 처리 합 니 다.
    2. N 의 왼쪽 아이 가 비어 있 으 면 스 택 꼭대기 요 소 를 꺼 내 스 택 작업 을 하고 스 택 꼭대기 노드 를 방문 한 다음 에 스 택 꼭대기 요소 의 오른쪽 아 이 를 N 으로 설정 합 니 다.
    3. N 이 비어 있 고 스 택 이 비어 있 을 때 까지 반복 합 니 다.
참고 자료: 이 진 트 리 의 비 재 귀적 옮 겨 다 니 기
코드 는 다음 과 같 습 니 다:
/**
 * 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 inorderTraversal(TreeNode* root) {
        if(root == nullptr) return vector();
        
        stack stk;
        vector ans;
        TreeNode* now = root;
        
        while(now || stk.size()){
            while(now){
                stk.push(now);
                now = now->left;
            }
            
            if(stk.size()){
                now = stk.top();
                ans.push_back(now->val);
                stk.pop();
                now = now->right;
            }
        }
        return ans;
    }
};

좋은 웹페이지 즐겨찾기