[LeetCode]144. Binary Tree Preorder Traversal
For example: Given binary tree
{1,#,2,3}
, 1
\
2
/
3
return
[1,2,3]
. Note: Recursive solution is trivial, could you do it iteratively?
방법
앞의 두 갈래 나무가 두루 다니니 귀속할 방법이 없으니 창고를 빌려야 한다.먼저 루트를 창고에 넣고 꺼내서 오른쪽 노드를 창고에 넣고 왼쪽 노드를 창고에 넣는다.그리고 창고의 노드를 꺼내 이 노드의 오른쪽, 왼쪽 노드를 눌러 창고가 비어 있을 때까지 순환하면 된다.
c 코드
#include
#include
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
if(root == NULL)
return NULL;
int *vals = (int *)malloc(sizeof(int) * 1000);
int valsTop = 0;
struct TreeNode* node = root;
struct TreeNode** nodes = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 1000);
int nodesTop = 0;
nodes[nodesTop++] = root;
while(nodesTop > 0) {
node = nodes[--nodesTop];
vals[valsTop++] = node->val;
if(node->right)
nodes[nodesTop++] = node->right;
if(node->left)
nodes[nodesTop++] = node->left;
}
*returnSize = valsTop;
return vals;
}
int main() {
struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node1_2 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node1_2->val = 2;
root->left = NULL;
root->right = node1_2;
struct TreeNode* node2_3 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node2_3->val = 3;
node1_2->left = node2_3;
node1_2->right = NULL;
node2_3->left = NULL;
node2_3->right = NULL;
int returnSize = 0;
int* vals = preorderTraversal(root, &returnSize);
assert(returnSize == 3);
assert(vals[0] == 1);
assert(vals[1] == 2);
assert(vals[2] == 3);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.