首页 > 代码库 > Binary Tree Inorder Traversal--leetcode
Binary Tree Inorder Traversal--leetcode
原题链接:https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
题目大意:中序遍历二叉树
解题思路:中序遍历二叉树。中序遍历二叉树的左子树,訪问根结点,中序遍历二叉树的右子树。非递归实现时,用一个栈模拟遍历过程就可以。由于须要先遍历左子树。所以每一个结点先入栈。出栈时訪问。
vector<int> inorderTraversal(TreeNode *root) { vector<int> ret; if(!root) return ret; stack<TreeNode*> s; while(root||!s.empty()) { if(!root) { root=s.top(); ret.push_back(root->val); s.pop(); root=root->right; } else { s.push(root); root=root->left; } }
复杂度分析:时间复杂度为O(N),由于每一个结点仅遍历一次。
空间复杂度为O(lgN)。为栈的最大长度。即树深。
中序遍历和先许遍历一样须要熟练掌握,bug-free哦。
Binary Tree Inorder Traversal--leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。