LeetCode | Binary Tree Inorder Traversal

题目

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively

老套路，递归（解法1）和非递归（解法2）各来一遍。

解法1

import java.util.ArrayList;

public class BinaryTreeInorderTraversal {
	public ArrayList
  
    inorderTraversal(TreeNode root) {
		ArrayList
   
     list = new ArrayList
    
     (); solve(root, list); return list; } private void solve(TreeNode root, ArrayList
     
       list) { if (root == null) { return; } solve(root.left, list); list.add(root.val); solve(root.right, list); } }
     
    
   
  

import java.util.ArrayList;
import java.util.Stack;

public class BinaryTreeInorderTraversal {
	public ArrayList
  
    inorderTraversal(TreeNode root) {
		ArrayList
   
     list = new ArrayList
    
     (); Stack
     
       stack = new Stack
      
       (); while (root != null) { stack.push(root); root = root.left; } while (!stack.isEmpty()) { TreeNode node = stack.pop(); list.add(node.val); TreeNode right = node.right; while (right != null) { stack.add(right); right = right.left; } } return list; } }