LeetCode 144. Binary Tree Preorder Traversal

一 题目

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

Example:

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

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

二 分析

题目都说了，递归是容易的，能否用迭代实现？

没尝试啊，先用递归写一版。

public class Code144 { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } List<Integer> list = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs(TreeNode root){ if(root == null) { return; } list.add(root.val); dfs(root.left); dfs(root.right); } }

 

2 TODO 迭代

待补充。挖个坑。

填上：

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack stack = new Stack(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = (TreeNode) stack.pop(); if(node != null) { list.add(node.val); stack.push(node.right); stack.push(node.left); } } return list; }

太慢了。