Given a binary tree, return the inorder traversal of its nodes' values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2]
Challenge
Can you do it without recursion?
思路
解法一:
Traverse
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public ArrayList<Integer> inorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); traverse(root, result); return result; } public void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } traverse(root.left, result); result.add(root.val); traverse(root.right, result); } }
解法二:
Divide & Conquer
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public ArrayList<Integer> inorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } ArrayList<Integer> left = inorderTraversal(root.left); ArrayList<Integer> right = inorderTraversal(root.right); result.addAll(left); result.add(root.val); result.addAll(right); return result; } }
解法三:
Iterative
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Inorder in ArrayList which contains node values. */ public ArrayList<Integer> inorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (!stack.isEmpty() || curr != null) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; } }