首页 > 代码库 > Binary Tree Inorder Traversal [leetcode] 非递归的三种解法
Binary Tree Inorder Traversal [leetcode] 非递归的三种解法
第一种方法是Morris Traversal
是O(n)时间复杂度,且不需要额外空间的方法。缺点是需要修改树。
通过将叶子节点的right指向其中序后继。
代码如下
vector<int> inorderTraversal(TreeNode *root) { vector<int> res; TreeNode * cur = root; TreeNode * pre = NULL; while (cur) { if (cur->left == NULL) { res.push_back(cur->val); cur = cur->right; } else { pre = cur->left; while (pre->right && pre->right != cur) pre = pre->right; if (pre->right == NULL) { pre->right = cur; cur = cur->left; } if (pre->right == cur) { pre->right = NULL; res.push_back(cur->val); cur = cur->right; } } } return res; }
第二种方法利用栈,模拟递归过程
vector<int> inorderTraversal(TreeNode *root) { vector<int> res; vector<TreeNode*> stack; stack.push_back(root); set<TreeNode*> visited; while (stack.size()) { TreeNode * cur = stack.back(); stack.pop_back(); if (!cur) continue; if (visited.find(cur) == visited.end())//visited for the first time { stack.push_back(cur->right); stack.push_back(cur); stack.push_back(cur->left); visited.insert(cur); } else//visited for the second time res.push_back(cur->val); } return res; }
第三种方法来自《数据结构》
将所有左子节点入栈,当没有左子结点时取栈顶元素打印并转移到右子节点
vector<int> inorderTraversal(TreeNode *root) { vector<int> res; vector<TreeNode*> stack; TreeNode* cur = root; while (stack.size() || cur) { if (cur) { stack.push_back(cur); cur = cur->left; } else { cur = stack.back(); stack.pop_back(); res.push_back(cur->val); cur = cur->right; } } return res; }
Binary Tree Inorder Traversal [leetcode] 非递归的三种解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。