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?
题意：前序遍历二叉树。
思路：
1、分治的方法递归遍历中左右
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
helper(root, res);
return res;
}
private void helper(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
res.add(node.val);
helper(node.left, res);
helper(node.right, res);
}
-
通过栈来记录当前遍历节点的右节点，达到中左右的遍历效果。
public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) { return res; } //stack记录右边待遍历的节点 Stack<TreeNode> stack = new Stack<>(); while (root != null) { res.add(root.val); if (root.right != null) { stack.add(root.right); } root = root.left; if (root == null && !stack.isEmpty()) { root = stack.pop(); } } return res; }
