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);
}
-
通過棧來記錄當(dāng)前遍歷節(jié)點的右節(jié)點痹换，達到中左右的遍歷效果蜜暑。
public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) { return res; } //stack記錄右邊待遍歷的節(jié)點 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; }
