从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容器