LeetCode 94——二叉树的中序遍历

mac2024-01-26  35

一、题目介绍

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]    1     \      2     /    3

输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗?

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

本题采用迭代方法,利用栈来模拟递归调用,具体详见代码。

三、解题代码

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> vec; if(root == NULL) return vec; else { stack<TreeNode*> st; TreeNode* ptemp = root; while(ptemp || !st.empty()) { //左子树遍历到叶子节点 while(ptemp) { st.push(ptemp); ptemp = ptemp->left; } if(!st.empty()) { ptemp = st.top(); vec.push_back(ptemp->val); st.pop(); ptemp = ptemp->right; } } } return vec; } };

四、解题结果

最新回复(0)