94.binary-tree-inorder-traversa

题目：

94.binary-tree-inorder-traversa

解答：

迭代方法：

栈

/**
 * 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) {
        if(root == nullptr) return {};
        TreeNode* curNode = root;
        stack<TreeNode*> s;
        vector<int> ans;
        while(curNode != nullptr || !s.empty()){
            while(curNode != nullptr){
                s.push(curNode);
                curNode = curNode->left;
            }
            curNode = s.top();s.pop();
            ans.push_back(curNode->val);
            curNode = curNode->right;
        }
        return ans;
    }
};

递归方法:

关键是构造一个辅助函数

/**
 * 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> ans;
        inorderTraversal(root,ans);
        return ans;
    }
private:
    void inorderTraversal(TreeNode* root,vector<int>& ans){
        // 递归终止条件
        if(root == NULL) return;
        // 先访问左子树，再访问根节点，再访问右子树
        inorderTraversal(root->left, ans);
        ans.push_back(root->val);
        inorderTraversal(root->right,ans);
    }
};