题目地址:https://leetcode.com/problems/binary-tree-preorder-traversal/description/
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?
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
非递归(迭代版):
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
list.add(root.val);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return list;
}
}
递归版:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preorder(list, root);
return list;
}
public void preorder(List<Integer> list, TreeNode root) {
if (root == null) {
return ;
}
list.add(root.val);
preorder(list, root.left);
preorder(list, root.right);
}
}
Debug code in playground:
/* -----------------------------------
* WARNING:
* -----------------------------------
* Your code may fail to compile
* because it contains public class
* declarations.
* To fix this, please remove the
* "public" keyword from your class
* declarations.
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preorder(list, root);
return list;
}
public void preorder(List<Integer> list, TreeNode root) {
if (root == null) {
return ;
}
list.add(root.val);
preorder(list, root.left);
preorder(list, root.right);
}
}
public class MainClass {
public static TreeNode stringToTreeNode(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return null;
}
String[] parts = input.split(",");
String item = parts[0];
TreeNode root = new TreeNode(Integer.parseInt(item));
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
int index = 1;
while(!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int leftNumber = Integer.parseInt(item);
node.left = new TreeNode(leftNumber);
nodeQueue.add(node.left);
}
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int rightNumber = Integer.parseInt(item);
node.right = new TreeNode(rightNumber);
nodeQueue.add(node.right);
}
}
return root;
}
public static String integerArrayListToString(List<Integer> nums, int length) {
if (length == 0) {
return "[]";
}
String result = "";
for(int index = 0; index < length; index++) {
Integer number = nums.get(index);
result += Integer.toString(number) + ", ";
}
return "[" + result.substring(0, result.length() - 2) + "]";
}
public static String integerArrayListToString(List<Integer> nums) {
return integerArrayListToString(nums, nums.size());
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
TreeNode root = stringToTreeNode(line);
List<Integer> ret = new Solution().preorderTraversal(root);
String out = integerArrayListToString(ret);
System.out.print(out);
}
}
}