传送门：144. 二叉树的前序遍历
题目很简单，二叉树的前序遍历。若是使用递归进行实现十分的简单，但是今天我们使用非递归的形式进行实现。首先我们需要从递归中衍生出来，因为前序遍历首先先打印根节点，之后再进行其他处理。我们不妨将一棵树分解成根节点加左子树与右子树。每次遇到根节点就直接打印，之后将当前节点入栈，并继续访问其左子树，一直到左子树为空。之后根据栈顶元素回溯，访问当前栈顶元素的右子树，完成一次循环。并将该右子树视作一个全新的树，再次依次遍历其左节点，之后再进行回溯。
vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> s; //使用栈暂存走过的左节点 vector<int> v; //vector存储节点数据 TreeNode* cur = root; if(root == nullptr) return v; //空树返回空的vector while(cur||s.size()) //只要当前节点或栈不为空则需要继续走 { while(cur) //直到当前节点为空 { v.push_back(cur->val); //记录当前节点 s.push(cur); //左节点都入栈 cur = cur->left; //继续访问左节点 } cur = s.top()->right; //回溯访问栈顶元素的右子树 s.pop(); //出栈 } return v; }
第二题则是中序遍历，需要注意的便是中序遍历需要左节点先写入再写入根节点。因此需要调整节点写入的时机。因此不妨我们在回溯后再进行写入，此时便能保证当前的节点为左根右的顺序进行打印。
vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> v; if(root == nullptr) return v; TreeNode* cur = root; while(cur||s.size()) { while(cur) //直到空才结束 { s.push(cur); //左节点入栈 cur = cur->left; //继续访问左节点 } cur = s.top(); //回溯上一个左节点 s.pop(); v.push_back(cur->val); //写入当前节点 cur = cur->right; //访问当前节点右子树 } return v; }
