Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}
,1 \ 2 / 3
return
[1,3,2]
.
Note: Recursive solution is trivial, could you do it iteratively?
Solution 1: recursive
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
travel(root, res);
return res;
}
private void travel(TreeNode x, List<Integer> res){
if (x==null) return;
travel(x.left,res);
res.add(x.val);
travel(x.right,res);
}
}
Solution 2: iterative
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
List<Integer> res=new ArrayList<>();
TreeNode x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
res.add(x.val);
x=x.right;
}
}
return res;
}
}
没有评论:
发表评论