从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145（中）：https://developer.aliyun.com/article/1521950
144. 二叉树的前序遍历 - 力扣（LeetCode）
难度简单
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { };
解析代码：
这道题用C语言写过递归版本的，当时说了后面会用非递归写，兑现承诺了属于是：
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)_GR C的博客-CSDN博客
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while(cur || !st.empty()) // 开始访问每一颗树，最后再写退出循环的条件 { while(cur) // 1.左路结点的值直接输出，结点入栈 { v.push_back(cur->val); st.push(cur); cur = cur->left; } TreeNode* top = st.top(); // 2.访问左路结点的右子树 st.pop(); cur = top->right; // 子问题回到循环访问右子树，非递归的精髓 } return v; } };
94. 二叉树的中序遍历 - 力扣（LeetCode）
难度简单
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { } };
解析代码：
上面也有其它思路，但我们上面的思路前中后序遍历的思路是互通的，只是输出时机不同
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while(cur || !st.empty()) // 开始访问每一颗树 { while(cur) // 1.左路结点入栈 { st.push(cur); cur = cur->left; } // 当这个结点从栈出来,表明这个结点的左路结点已经访问了 TreeNode* top = st.top(); st.pop(); v.push_back(top->val); // 2. 输出这个结点 cur = top->right; // 子问题回到循环访问右子树，非递归的精髓 } return v; } };
145. 二叉树的后序遍历 - 力扣（LeetCode）
难度简单
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { } };
解析代码：
后序和前面两个有点不一样，当你左路结点访问了，这时如果你的右结点为空，
你可以输出根结点，否则要访问右结点，访问右结点之后，回到根结点，
根结点的右结点还是不为空，所以根结点的右结点访问过了的情况也要输出根结点：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; TreeNode* prev = nullptr; while(cur || !st.empty()) // 开始访问每一颗树 { while(cur) // 1.左路结点入栈 { st.push(cur); cur = cur->left; } // 当这个结点从栈出来,表明这个结点的左路结点已经访问了 TreeNode* top = st.top(); if(top->right == nullptr || prev == top->right) //如果右为空或者上一个输出的结点是右 { v.push_back(top->val); // 2. 输出这个结点 prev = top; // 记录上一个输出的结点 st.pop(); } else { cur = top->right; // 子问题回到循环访问右子树，非递归的精髓 } } return v; } };
本章完。
下一部分：set和map容器
