Reverse Integer（逆转整数）

2019-01-09

字数统计: 243字 | 阅读时长≈ 1分

94. Binary Tree Inorder Traversal

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

Example:
Input: [1,null,2,3]
1

2
/
3

Output: [1,3,2]

1.recursive solution

/**
 * Definition for a binary tree node.
 * 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> res;
        if (root != NULL) {
            res = inorderTraversal(root->left);
            res.push_back(root->val);
            vector<int> right_res = inorderTraversal(root->right);
            res.insert(res.end(), right_res.begin(), right_res.end());    
        }
        return res;
    }
};

2.iterative solution

/**
 * Definition for a binary tree node.
 * 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> res;
        stack<TreeNode*> s;

        if (root != NULL) {
           TreeNode* cur = root;
           s.push(cur);
           while (cur->left != NULL) {
               s.push(cur->left);
               cur = cur->left;
           }

           while(!s.empty()) {
                TreeNode* tmp = s.top();
                s.pop();
                res.push_back(tmp->val);
                if (tmp->right != NULL) {
                    cur = tmp->right;
                    s.push(cur);
                    while (cur->left != NULL) {
                        s.push(cur->left);
                        cur = cur->left;
                    } 
                } 
           }
        }
        
        return res;
    }
};

本文作者： John Doe
本文链接： http://example.com/2019/01/09/algorithm/95. Binary Tree Inorder Traversal/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！