题解 | #二叉树的中序遍历#

vector<int> InOrder(TreeNode* head){
    vector<int> ans;
    vector<TreeNode*> helpans;
    TreeNode* index = head;
    TreeNode* temp = NULL;
    if(head == NULL)    return ans;
    while(index != NULL){
        helpans.push_back(index);
        index = index->left;
    }
    while(!helpans.empty()){
        temp = helpans.back();
        ans.push_back(temp->val);
        helpans.pop_back();
        index = temp->right;
        while(index != NULL){
            helpans.push_back(index);
            index = index->left;
        }
    }
    return ans;
}

不知道为啥核心代码模式一直编译错误，所以我直接用模板提交了，讲一下算法流程和思路。

根左右->根右左->左右根

预处理：头节点的左边界入栈

---------------------------------------------------------------------------------------------------

1) 处理cur节点(左边界最左那个)

2) 弹出cur节点

3) cur节点左孩子的右边界入栈

---------------------------------------------------------------------------------------------------

栈空时跳出