最好的网站建设哪家好,js特效网站欣赏,石家庄新钥匙做网站,网站内容及实现方式【每日刷题】Day130 #x1f955;个人主页#xff1a;开敲#x1f349; #x1f525;所属专栏#xff1a;每日刷题#x1f34d; #x1f33c;文章目录#x1f33c;
1. 144. 二叉树的前序遍历 - 力扣#xff08;LeetCode#xff09;
2. 94. 二叉树的中序遍历 - 力扣…【每日刷题】Day130 个人主页开敲 所属专栏每日刷题 文章目录
1. 144. 二叉树的前序遍历 - 力扣LeetCode
2. 94. 二叉树的中序遍历 - 力扣LeetCode
3. 145. 二叉树的后序遍历 - 力扣LeetCode 1. 144. 二叉树的前序遍历 - 力扣LeetCode //思路非递归。 //递归进行遍历二叉树非常简单但是非递归就要麻烦很多了。 class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint ans; stackTreeNode* st;//存放节点的栈 TreeNode* cur root; while(cur||!st.empty()) { while(cur)//一路往左遍历到空 { ans.push_back(cur-val); st.push(cur); cur cur-left; } TreeNode* tmp st.top();//获取栈顶节点也就是返回上一个节点 st.pop(); cur tmp-right;//去右子树继续重复上述过程 } return ans; } }; 2. 94. 二叉树的中序遍历 - 力扣LeetCode //思路非递归。 //基本思路与 前序遍历 的非递归基本一致。唯一的区别在于访问根节点值的时机。 // 前序遍历 中 cur 在遍历的同时就记录了根节点的值。而中序遍历我们需要在 cur 往左遍历到空后记录根节点的值。 class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint ans; stackTreeNode* st; TreeNode* cur root; while(cur||!st.empty()) { while(cur)//往左遍历到空并将节点放入栈中 { st.push(cur); cur cur-left; } ans.push_back(st.top()-val);//记录根节点值 TreeNode* tmp st.top(); st.pop(); cur tmp-right; } return ans; } }; 3. 145. 二叉树的后序遍历 - 力扣LeetCode //思路非递归。 //思路大体上还是相同的但是细节的处理多了很多。 //首先还是让 cur 往左遍历到空。随后 tmp 获取栈顶元素此时分为三种情况 //① 如果 tmp-right 为空说明此时 tmp 为叶子节点将值放入 ans 数组中 //② 如果 tmp-right 不为空说明还有右子树cur 去到 tmp-right //③ 这种情况最麻烦tmp-right 不为空但是 tmp-right 的节点的值我们已经存储过了从 tmp-right 回到根节点此时我们也是需要记录 tmp-val 的。 //但是根据我们①、②点的逻辑是没法做到的并且会陷入死循环因为会一直走 cur tmp-right 的逻辑 //因此这里我们需要用一个变量 prev 来记录存储过的 tmp-right 节点 class Solution { public: vectorint postorderTraversal(TreeNode* root) { vectorint ans; stackTreeNode* st; TreeNode* cur root; TreeNode* prev nullptr; while(cur||!st.empty()) { while(cur) { st.push(cur); cur cur-left; } TreeNode* tmp st.top(); //前面思路相同 if(!tmp-right||tmp-rightprev)//如果tmp-rightprev说明 tmp-right 已经记录过也可以理解为从tmp-right 回来了此时 tmp-val也要记录因为左右子树都遍历完了 { ans.push_back(tmp-val); st.pop(); prev tmp;//使用 prev 记录存储过的 tmp-right } else cur tmp-right; } return ans; } };
