题目链接

    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 {
    18.     // 1.之前写的，使用栈保存, 0ms，100.00%
    19.     public List<Integer> preorderTraversal1(TreeNode root) {
    20.         List<Integer> list = new ArrayList<>();
    21.         // preRoot(root, list);
    22.         if(root == null) {
    23.             return list;
    24.         }
    25.         //通过栈进行迭代
    26.         Stack<TreeNode> stack = new Stack<>();
    27.         stack.push(root);
    28.         while(!stack.isEmpty()) {
    29.             TreeNode node = stack.pop();
    30.             list.add(node.val);
    31.             if(node.right != null) {
    32.                 stack.push(node.right);
    33.             }
    34.             if(node.left != null) {
    35.                 stack.push(node.left);
    36.             }
    37.         }
    38.         return list;
    39.     }
    41.     //前序递归
    42.     public void preRoot(TreeNode root, List<Integer> list) {
    43.         if(root != null) {
    44.             list.add(root.val);
    45.             preRoot(root.left, list);
    46.             preRoot(root.right, list);
    47.         }
    48.     }
    50.     //中序递归
    51.     public void preRoot2(TreeNode root, List<Integer> list) {
    52.         if(root != null) {
    53.             preRoot(root.left, list);
    54.             list.add(root.val);
    55.             preRoot(root.right, list);
    56.         }
    57.     }
    59.     //后序递归
    60.     public void preRoot3(TreeNode root, List<Integer> list) {
    61.         if(root != null) {
    62.             preRoot(root.left, list);
    63.             preRoot(root.right, list);
    64.             list.add(root.val);
    65.         }
    66.     }
    68.     // 2. 0ms，100.00%
    69.     public List<Integer> preorderTraversal(TreeNode root) {
    70.         List<Integer> list = new ArrayList<>();
    71.         preRoot(root, list);
    73.         return list;
    74.     }
    75. }