이 진 트 리 앞 순서 옮 겨 다 니 기

제목:
두 갈래 나 무 를 주 고 노드 값 의 앞 순 서 를 되 돌려 줍 니 다.
당신 은 실제 면접 에서 이 문 제 를 만난 적 이 있 습 니까? 
Yes
본보기
이 진 트 리 한 그루 를 드 리 겠 습 니 다.  {1,#,2,3} ,
   1
    \
     2
    /
   3

 되돌아오다  [1,2,3]
사고: 먼저 벡터 ss 와 배열 s 를 구축 하고 top = - 1 을 정의 하 며 root! =null 혹은 top! = -1 시, 루트 의 값 을 ss 에 삽입 합 니 다. top 에 1 을 추가 하여 s [top] 를 root 와 같 게 합 니 다. root 는 왼쪽 아들 과 같 습 니 다. 만약 top! = -1, top -, root 를 s [top] 로 바 꾸 고 root 를 아들 로 바 꾸 고 마지막 에 ss 로 돌아 갑 니 다.
코드:
/**  * Definition of TreeNode:  * class TreeNode {  * public:  *     int val;  *     TreeNode *left, *right;  *     TreeNode(int val) {  *         this->val = val;  *         this->left = this->right = NULL;  *     }  * }  */ class Solution { public:     /**      * @param root: The root of binary tree.      * @return: Preorder in vector which contains node values.      */     vector preorderTraversal(TreeNode *root) {         // write your code here         vectorss;         TreeNode *s[100];        int top=-1;        while(root!=NULL||top!=-1)        {            while(root!=NULL)            {                //coutval);                s[++top]=root;                root=root->left;            }            if(top!=-1)            { root=s[top--];              root=root->right;            }        }        return ss;     } };
소감: 이 문제 의 top 사용 느낌 이 매우 교묘 합 니 다. 저 는 교과 서 를 본 후에 여러 개의 그림 을 그 려 서 top 의 사용 을 알 게 되 었 습 니 다. 처음에 밖 에 ss 가 정의 되 지 않 아서 교체 할 수 없다 고 생각 했 기 때문에 이 알고리즘 을 사 용 했 습 니 다. 어렵 습 니 다.

좋은 웹페이지 즐겨찾기