LeetCode | Binary Tree Preorder Traversal

题目

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

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

   1
    \
     2
    /
   3

return [1,2,3].

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

二叉树的先序遍历，递归和非递归两种实现方法。

在非递归实现中，使用栈来保存访问顺序。

代码

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

public class BinaryTreePreorderTraversal {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public ArrayList
  
    preorderTraversal(TreeNode root) {
		ArrayList
   
     list = new ArrayList
    
     (); // recursivePreorderTraversal(root, list); iterativePreorderTraversal(root, list); return list; } private void iterativePreorderTraversal(TreeNode root, ArrayList
     
       list) { if (root == null) { return; } Stack
      
        stack = new Stack
       
        (); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); while (node != null) { list.add(node.val); if (node.right != null) { stack.push(node.right); } node = node.left; } } } private void recursivePreorderTraversal(TreeNode root, ArrayList
        
          list) { if (root == null) { return; } list.add(root.val); recursivePreorderTraversal(root.left, list); recursivePreorderTraversal(root.right, list); } }