Leetcode 144 - Binary Tree Preorder Traversal（二叉树前序遍历）

题意

求二叉树的前序遍历。

思路

分为递归实现和利用栈模拟递归实现。 递归实现的代码和思路很简单就不详细说了。关键是我们如何利用栈非递归的去实现。 关键思路就是：对于当前节点，我们递归的去对它的左子树和右子树做相同的操作。 考虑前序遍历的过程： 假设当前节点为p，当p有左子树的时候，我们去访问p的左子树。如果p有右子树，我们去访问p的右子树。

算法1

利用栈先进后出的特点： 1. 加入根节点。 2. 我们每次从栈顶取元素访问，并先加入其右儿子，再加入其左儿子。 重复上述过程直到栈为空。

算法2

更像利用迭代改为栈实现的思路。 对于当前节点p，我们去访问它的右子树的充要条件是：当且仅当p的左子树全部被访问。 那么，就可以得到我们的算法： 1. 初始化一个栈s和指针p指向根节点。 2. 如果s非空或者p != null：   1. 如果p != null：说明p还没有被访问。我们访问p，并且将p送入栈里面（以便访问右子树的时候能够获取到当前状态）并且p指向其左儿子（先访问左子树）。   2. 如果p == null：说明这时候左边的节点已经全部访问完毕了，我们需要返回到其父节点，然后访问右子树。其父节点的状态保存在s中，于是我们从s中pop出一个节点，并且p指向其右儿子。 3. 重复上一步直到不满足。

代码

algorithm 1

class Solution { private: vector<int> ans; public: void dfs(TreeNode *root) { if (!root) return; ans.push_back(root->val); dfs(root->left); dfs(root->right); } vector<int> preorderTraversal(TreeNode* root) { dfs(root); return ans; } };

algorithm 2

class Solution { private: vector<int> ans; public: vector<int> preorderTraversal(TreeNode* p) { stack<TreeNode*> s; while (p || s.size()) { if (p) { ans.push_back(p->val); s.push(p); p = p->left; } else { p = s.top(); s.pop(); p = p->right; } } return ans; } };

algorithm 3

class Solution { private: vector<int> ans; public: vector<int> preorderTraversal(TreeNode* root) { if (root) { stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode *p = s.top(); s.pop(); ans.push_back(p->val); if (p->right) s.push(p->right); if (p->left) s.push(p->left); } } return ans; } };