二叉树中序遍历
递归实现:
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- if(!root) return result;
- inorderCore(root);
- return result;
- }
- void inorderCore(TreeNode* root) {
- if(root->left) inorderCore(root->left);
- result.push_back(root->val);
- if(root->right) inorderCore(root->right);
- }
- private:
- vector<int> result;
- };
非递归实现.
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- vector<int> result;
- stack<TreeNode*> tmp;
- TreeNode* node = root;
- TreeNode* cur;
- while(node || !tmp.empty()) {
- while(node) {
- tmp.push(node);
- node = node->left;
- }
- node = tmp.top();
- tmp.pop();
- result.push_back(node->val);
- node = node->right;
- }
- return result;
- }
- };
分析:
1, 使用堆栈作为存储结构
2, 当节点不为空或者堆栈, 每次根据给定节点对其左子树进行入栈.
3, 出栈, 并且保存节点值, 然后将右节点赋给当前节点 (不用判断是否为空, 若为空, 刚好不用进行左节点遍历的步骤)
来源: http://www.bubuko.com/infodetail-3261075.html