来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个二叉树,返回它的中序遍历。
例如输入: [1,null,2,3]
1 2 3 4 5 |
1 \ 2 / 3 |
输出:
1 |
[1,3,2] |
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
二、题解
三、代码
3.1 非递归代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode *> st; TreeNode *p; p = root; while (p || !st.empty()) { // 循环遍历左子树 while (p) { st.push(p); p = p->left; } if (!st.empty()) { // 弹出栈顶节点 p = st.top(); st.pop(); // 访问节点 v.push_back(p->val); // 访问右子树 p = p->right; } } return v; } }; |
3.2 递归代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: void inorderTraversal(TreeNode *root, vector<int> &v) { if (root == nullptr) { return ; } if (root->left) { inorderTraversal(root->left, v); } v.push_back(root->val); if (root->right) { inorderTraversal(root->right, v); } } public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; inorderTraversal(root, v); return v; } }; |
评论