《leetCode》:Binary Tree Inorder Traversal

제목

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

생각


제목은 비교적 간단하다. 바로 두 갈래 나무의 중서열을 구하고 두 갈래 나무에 관해서는 귀속으로 실현하는 것이 비교적 쉽다.두 갈래 나무의 중간 순서 (왼쪽 루트 오른쪽) 의 정의에 따라 코드를 작성하면 됩니다.
구현 코드는 다음과 같습니다.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
void my_inorderTraversal(struct TreeNode* root, int* res,int* returnSize){
    if(root==NULL){
        return ;
    }
    // 
    if(root->left!=NULL){
        my_inorderTraversal(root->left, res,returnSize);
    }
    // 
    res[(*returnSize)]=root->val;
    (*returnSize)++;
    // 
    if(root->right!=NULL){
        my_inorderTraversal(root->right, res,returnSize);
    }

}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    if(root==NULL){
        return NULL;
    }
    // 
    int *res=(int *)malloc(100*sizeof(int));
    if(res==NULL)
        exit(EXIT_FAILURE);
    *returnSize=0;
    my_inorderTraversal(root,res,returnSize);
    return res;

}

좋은 웹페이지 즐겨찾기