이 진 트 리 앞 순서 옮 겨 다 니 기
1756 단어 데이터 구조 이 진 트 리
두 갈래 나 무 를 주 고 노드 값 의 앞 순 서 를 되 돌려 줍 니 다.
당신 은 실제 면접 에서 이 문 제 를 만난 적 이 있 습 니까?
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) { //cout
소감: 이 문제 의 top 사용 느낌 이 매우 교묘 합 니 다. 저 는 교과 서 를 본 후에 여러 개의 그림 을 그 려 서 top 의 사용 을 알 게 되 었 습 니 다. 처음에 밖 에 ss 가 정의 되 지 않 아서 교체 할 수 없다 고 생각 했 기 때문에 이 알고리즘 을 사 용 했 습 니 다. 어렵 습 니 다.