- 描述
Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree
{1, #, 2, 3}, return [1, 2, 3].
Note: Recursive solution is trivial, could you do it iteratively?
使用非递归进行先序遍历，要借助栈（后进先出），先把左子树依次进栈，存入到结果集，这时候结果集保留了左子树的节点值，接着弹栈，如果弹出的节点有右子树，则把右子树进栈，并保存到结果集
时间复杂度O(n)，空间复杂度O(n)
中序遍历只需要把输出结果的位置调换一下即可
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution {
public List<Integer> inorderTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()) {
if(p != null) {
stack.push(p);
result.add(p.val);
p = p.left;
}
else {
p = stack.pop();
p = p.right;
}
}
return result;
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// 解法2， 深度优先搜索DFS的思想
public class Solution1 {
public static List<Integer> preorderTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
result.add(p.val);
if(p.right != null) stack.push(p.right);
if(p.left != null) stack.push(p.left);
}
return result;
}
}
