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: vectorint inorderTraversal(TreeNode* root) { vectorint res; inOrder(root,res); return res; } void inOrder(TreeNode* node,vectorint 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: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* s; TreeNode* currroot; while(curr!NULL||!s.empty()){ while(curr!NULL){ s.push(curr); currcurr-left; } //左子树为空但栈不为空的情况 currs.top(); s.pop(); res.push_back(curr-val); currcurr-right; } return res; } };