LeeCode HOT 100 94.二叉树的中序遍历

给定一个二叉树的根节点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) { vector<int> res; inOrder(root,res); return res; } void inOrder(TreeNode* node,vector<int>& res){ if(!node)return; inOrder(node->left,res); res.push_back(node->val); inOrder(node->right,res); } };

迭代算法:

/** * 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) { vector<int> res; stack<TreeNode*> s; TreeNode* curr=root; while(curr!=NULL||!s.empty()){ while(curr!=NULL){ s.push(curr); curr=curr->left; } //左子树为空但栈不为空的情况 curr=s.top(); s.pop(); res.push_back(curr->val); curr=curr->right; } return res; } };