电商网站建设网,免费ftp 网站,东莞 网站建设企业,广州城市建设档案馆网站作者#xff1a;小卢 专栏#xff1a;《Leetcode》 喜欢的话#xff1a;世间因为少年的挺身而出#xff0c;而更加瑰丽。 ——《人民日报》 144. 二叉树的前序遍历
144. 二叉树的前序遍历
题目#xff1a;
给你二叉树的根节点 root 小卢 专栏《Leetcode》 喜欢的话世间因为少年的挺身而出而更加瑰丽。 ——《人民日报》 144. 二叉树的前序遍历
144. 二叉树的前序遍历
题目
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 思路
我们可以将二叉树一直向走到底这样就会有一条道最左的路径我们将其称为左子路我们可以将二叉树分为左子路和左子路节点的右子树等等
我们利用一个栈来存储左子路如果到底就出栈顶然后遍历该栈顶的右子树以此循环
代码
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintv;TreeNode*curroot;while(cur||!st.empty()){while(cur){st.push(cur);v.push_back(cur-val);curcur-left;}TreeNode*topst.top();st.pop();curtop-right;}return v;}
}; 94. 二叉树的中序遍历
94. 二叉树的中序遍历
题目
给定一个二叉树的根节点 root 返回 它的 中序 遍历
示例 代码
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintv;TreeNode*curroot;while(cur||!st.empty()){while(cur){st.push(cur);curcur-left;}TreeNode*topst.top();st.pop();v.push_back(top-val);curtop-right;}return v;}
}; 145. 二叉树的后序遍历 145. 二叉树的后序遍历 题目
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 代码
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintv;TreeNode*curroot;TreeNode*prevnullptr;while(cur||!st.empty()){//左子路while(cur){st.push(cur);curcur-left;}//从栈里面取到左子路的节点TreeNode*topst.top();//这里右不存在或者右子树已经遍历了才可以//prev记录上一个节点如果prev是top的父亲就说明右子树已经遍历了if(top-rightnullptr||top-rightprev){v.push_back(top-val);st.pop();prevtop;}else{curtop-right;}}return v;}
};
