leetcode[96] Binary Tree Inorder Traversal

6249 단어 LeetCode
나무 뿌리를 정하다.중서 역행을 실현하는 것은 바로 왼쪽 뿌리와 오른쪽이다.
귀속을 사용하면 간단합니다. 왼쪽의 반환값에 루트를 더하고 오른쪽을 더하면 됩니다.
내가 쓴 것은 좀 좌절되었다.
/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root)

    {

        vector<int> lf, ri, ans;

        if (root == NULL) return ans;

        lf = inorderTraversal(root -> left);

        ri = inorderTraversal(root -> right);

        lf.push_back(root -> val);

        for (int i = 0; i < ri.size(); ++i)

        {

            lf.push_back(ri[i]);

        }

        return lf;

    }

};

사실 쓸 수 있어요간단하다 :
class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> vi;

        inHelper(root, vi);

        return vi;

    }



    void inHelper(TreeNode *node, vector<int>& vi)

    {

        if(node == nullptr) return;

        inHelper(node->left, vi);

        vi.push_back(node->val);

        inHelper(node->right, vi);

    }

};

제목은 귀속되지 않으면 다음과 같은 leetcode에서 창고를 이용하는 것이 좋습니다.
vector<int> inorderTraversal(TreeNode *root) 

    {

        vector<int> rs;

        if (!root) return rs;

        stack<TreeNode *> stk;

        TreeNode *p = root;

        while (!stk.empty() || p)

        {

            if (p)

            {

                stk.push(p);

                p = p->left;

            }

            else

            {

                p = stk.top();

                stk.pop();

                rs.push_back(p->val);

                p = p->right;

            }

        }

        return rs;

    }

 2014-12-13
/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root)

    {

        vector<int> perm;

        if (root == NULL) return perm;

        stack<TreeNode *> sta;

        

        TreeNode *p = root;

        

        while(!sta.empty() || p)

        {

            while (p)

            {

                sta.push(p);

                p = p -> left;

            }

            if (!sta.empty())

            {

                p = sta.top();

                sta.pop();

                perm.push_back(p -> val);

                p = p -> right;

            }

        }

        return perm;

    }

};

좋은 웹페이지 즐겨찾기