首页 > 代码库 > leetcode[96] Binary Tree Inorder Traversal
leetcode[96] Binary Tree Inorder Traversal
给定树根root。实现中序遍历，也就是左根右。
用递归的话，很简单，左边的返回值加上root的再加上右边的就行。
我自己写的有点挫：
/** * Definition for binary tree * 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> lf, ri, ans; if (root == NULL) return ans; lf = inorderTraversal(root -> left); ri = inorderTraversal(root -> right); lf.push_back(root -> val); for (int i = 0; i < ri.size(); ++i) { lf.push_back(ri[i]); } return lf; }};
其实可以写简单一些：
class Solution {public: vector<int> inorderTraversal(TreeNode *root) { vector<int> vi; inHelper(root, vi); return vi; } void inHelper(TreeNode *node, vector<int>& vi) { if(node == nullptr) return; inHelper(node->left, vi); vi.push_back(node->val); inHelper(node->right, vi); }};
题目要求如果不用递归的话，用如下leetcode上的，利用堆，很妙。
vector<int> inorderTraversal(TreeNode *root) { vector<int> rs; if (!root) return rs; stack<TreeNode *> stk; TreeNode *p = root; while (!stk.empty() || p) { if (p) { stk.push(p); p = p->left; } else { p = stk.top(); stk.pop(); rs.push_back(p->val); p = p->right; } } return rs; }
leetcode[96] Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。