前序遍历从根出发一路向左每经过一个节点就立刻访问它因为前序是先访问根同时把这个节点 记下来—— 因为等左子树走完还得回来走它的右子树一直走到左边没有节点了说明这一支的左子树全部走完了这时从 记下来 的节点里取出最近记的那一个去走它的右子树右子树又重复 一路向左走 的过程直到 记下来 的节点全部取完且当前也没有节点可走了遍历结束这里的 记下来 就是压栈取出最近记的那一个 就是弹栈。因为栈是后进先出的最近压进去的节点最先弹出来正好对应递归返回时回到最近的那一层调用。下面是代码实现vectorint preorderTraversal(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; vectorint v; while (cur || !st.empty()) { // 每次循环开始访问一棵树的开始 // 访问左路节点左路节点入栈 while (cur) { v.push_back(cur-val); st.push(cur); cur cur-left; } // 取一个左路节点的右子树出来访问 TreeNode* pos st.top(); st.pop(); // 循环子问题的访问访问右子树 cur pos-right; } return v; }中序遍历从根出发一路向左只把经过的节点压栈记下来不立刻访问中序要先把左全部走完才访问根。一直走到左边没有节点了说明这一支的左子树全部走完了。这时从“记下来”的节点里取出最近记的那一个现在访问这个节点这就是处理根。访问完成之后去走它的右子树。右子树又重复“一路向左压栈记节点”的整套过程。直到“记下来”的节点全部取完且当前也没有节点可走了遍历结束。“记下来”就是压栈“取出最近记的那一个”就是取栈顶。栈后进先出正好模拟递归返回回到最近一层调用。vectorint inorderTraversal(TreeNode* root) { stackTreeNode* st; vectorint v; TreeNode* cur root; while (cur || !st.empty()) { // 每次循环开始访问一棵树的开始 // 访问左路节点左路节点入栈 while (cur) { st.push(cur); cur cur-left; } // 取一个左路节点的右子树出来访问 TreeNode* pos st.top(); v.push_back(pos-val); st.pop(); // 循环子问题的访问访问右子树 cur pos-right; } return v; }后序遍历文字描述单栈版从根出发一路向左把经过的节点全部“记下来”压栈不访问。一直走到左边没有节点左子树走完。看栈顶节点如果它没有右孩子或者右孩子已经被访问过了说明左、右子树都处理完毕现在访问这个根节点如果还有未访问的右子树则转到右子树右子树重复“一路向左压栈”的过程。直到记下来的栈全部取完没有节点可走遍历结束。关键点后序必须确认右子树已经处理完才可以访问当前节点用 pre 记录上一个被输出的节点用来判断右子树是否处理完成。vectorint postorderTraversal(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; vectorint v; TreeNode* pre nullptr; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } // 取一个左路节点的右子树出来访问这时代表左路节点的左子树已经访问过了 TreeNode* pos st.top(); if (pos-right nullptr || pos-right pre) { v.push_back(pos-val); st.pop(); pre pos; } else { // 循环子问题的访问访问右子树 cur pos-right; } } return v; }