给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
image.png

递归:

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode() {}
  8. * TreeNode(int val) { this.val = val; }
  9. * TreeNode(int val, TreeNode left, TreeNode right) {
  10. * this.val = val;
  11. * this.left = left;
  12. * this.right = right;
  13. * }
  14. * }
  15. */
  16. class Solution {
  17. public List<Integer> preorderTraversal(TreeNode root) {
  18. List<Integer> keys = new ArrayList<>();
  19. preorderTraversal(root, keys);
  20. return keys;
  21. }
  22. public void preorderTraversal(TreeNode root, List<Integer> keys){
  23. if(root == null){
  24. return;
  25. }
  26. //先遍历根节点
  27. keys.add(root.val);
  28. //遍历左子树
  29. preorderTraversal(root.left, keys);
  30. //遍历右子树
  31. preorderTraversal(root.right, keys);
  32. }
  33. }

迭代:

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode() {}
  8. * TreeNode(int val) { this.val = val; }
  9. * TreeNode(int val, TreeNode left, TreeNode right) {
  10. * this.val = val;
  11. * this.left = left;
  12. * this.right = right;
  13. * }
  14. * }
  15. */
  16. class Solution {
  17. public List<Integer> preorderTraversal(TreeNode root) {
  18. List<Integer> list = new ArrayList<>();
  19. Stack<TreeNode> stack = new Stack<>();
  20. stack.push(root);
  21. while(!stack.isEmpty()){
  22. TreeNode node = stack.pop();
  23. if(node == null){
  24. continue;
  25. }
  26. list.add(node.val);
  27. //前序 遍历,栈的话,需要push先右后左
  28. if(node.right!=null){
  29. stack.push(node.right);
  30. }
  31. if(node.left!=null){
  32. stack.push(node.left);
  33. }
  34. }
  35. return list;
  36. }
  37. }