[leetcode]94. Binary Tree Inorder Traversal二叉树中序遍历

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

 

题意：

二叉树中序遍历

 

Solution1:   Recursion 

code

1 class Solution { 2 public List<Integer> inorderTraversal(TreeNode root) { 3 List<Integer> list = new ArrayList<>(); 4 storeInorder(root, list); 5 return list; 6 } 7 public void storeInorder(TreeNode node, List<Integer> list) { 8 if(node == null) return; 9 storeInorder(node.left, list); 10 list.add(node.val); 11 storeInorder(node.right, list); 12 } 13 }

 

Solution2:   Iteration

code

1 class Solution { 2 public List<Integer> inorderTraversal(TreeNode root) { 3 //left -- root -- right 4 ArrayList<Integer> result = new ArrayList<>(); 5 Stack<TreeNode> s = new Stack<>(); 6 TreeNode p = root; 7 8 while(!s.isEmpty() || p!=null){ 9 if(p!=null){ 10 s.push(p); 11 p = p.left; 12 }else{ 13 p =s.pop(); 14 result.add(p.val); 15 p = p.right; 16 } 17 } 18 return result; 19 } 20 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/10733619.html