首页 > 代码库 > 94. Binary Tree Inorder Traversal
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes‘ values.
For example:
Given binary tree [1,null,2,3],
1 2 / 3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Show Company Tags
Show Tags
Show Similar Problems
Recursive:
public IList<int> InorderTraversal(TreeNode root) { var res = new List<int>(); Recursive(root, res); return res; } public void Recursive(TreeNode root, IList<int> list) { if(root == null) return; if(root.left == null && root.right == null) { list.Add(root.val); return; } Recursive(root.left, list); list.Add(root.val); Recursive(root.right, list); }
Iteration:
此题的iteration的条件是最难把握的，因为如果每次stack push 左子树到底的时候，我们需要让loop的变量tree element指向该左元素的右子数。右子数可能为null， 此时就会跳出循环。解决方法是在循环条件里加上stack 不为空。只要不为空，则证明还有值需要iteration。
public IList<int> InorderTraversal(TreeNode root) { var res = new List<int>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(root != null || stack.Count() >0) { while(root != null) { stack.Push(root); root = root.left; } var a = stack.Pop(); res.Add(a.val); root = a.right;//cruz we have stack.Count() > 0 , no worry right is null } return res; }
94. Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。