LeetCode 二叉树的中序遍历

二叉树的中序遍历

二叉树的中序遍历 顺序其实就是 左 中 右
用递归的解法来解：

class Solution {
public:
void helper (TreeNode* root, vector<int>&a) {
if (root == NULL) {
return;
}

    if (root->left != NULL) {
        helper(root->left, a);//左
    }

    a.push_back(root->val);//中 把当前节点的值放到数组中去

    if (root->right != NULL) {
        helper(root->right, a);//右
    }

}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> a; 
    helper(root, a);
    return a;//返回最终结果
}

};

迭代解法：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode> s;
        vector<int> ans;
        TreeNode* t = root;
        while(t || !s.empty()){
            while(t){  //遍历到最左边的叶结点
                s.push(*t);
                t = t->left;
            }
            if(!s.empty()){
                ans.push_back(s.top().val);
                t = s.top().right;
                s.pop();
            }
        }
        return ans;
    }
};