【LeetCode】-- 144. 二叉树的前序遍历

1. 题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

2. 示例

示例一：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例二：

输入：root = []

输出：[]

示例三：

输入：root = [1]

输出：[1]

示例4：

输入：root = [1,2]

输出：[1,2]

3. 分析

如果用二叉树的非递归做这道题：

（1）把一棵树拆成两个部分去访问：左路节点，左路节点上的右子树

前序遍历就是根~左子树~根~左子树，左路节点访问完了，还剩左路节点上的右子树。

（2）访问左路节点时，同时入栈左路节点

（3）访问右子树时，先弹出左路节点，再访问它的右子树，不断拆解成子问题，用循环来做：

       1的左子树访问完了要访问1的右子树，1的右子树为空，还有3和5的右子树没访问，1作为3的左子树，3的左子树访问完了，要访问3的右子树，4和6访问完之后，要访问5的右树，7的左子树为空，访问完了就访问7的右子树8，8的左右子树都为空，结束。

完整过程如下：

 

 

 

4. 代码实现

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14. vector<int> preorderTraversal(TreeNode* root) {
15.         stack<TreeNode*> st;
16.         vector<int> ret;
17.         TreeNode* cur = root;
18. 
19. while(cur || !st.empty())//cur指向哪个节点就表示前序访问这棵树
20.         {
21. //1.访问左路节点，左路节点入栈，直到左路节点为空
22. while(cur)
23.             {
24.                 ret.push_back(cur->val);
25.                 st.push(cur);
26.                 cur = cur->left;
27.             }
28. 
29. //2.依次取左路节点的右子树出来访问
30.             TreeNode* top = st.top();
31.             st.pop();
32. 
33. //以子问题的形式访问这些右子树
34.             cur = top->right;
35.         }
36. 
37. return ret;
38.     }
39. };