class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, node5);
        TreeNode node2 = new TreeNode(2, node4, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node1 = new TreeNode(1, node2, node3);
        morrisPre(node1);
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> nums = new ArrayList<>();
        if(root == null){
            return nums;
        }else{
            nums.add(root.val);//每遍历一个节点时添加节点值
            nums.addAll(preorderTraversal(root.left));
            nums.addAll(preorderTraversal(root.right));
        }
        return nums;
    }
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> nums = new ArrayList<>();
    if(root == null){
        return nums;
    }else{
        nums.addAll(inorderTraversal(root.left));
        nums.add(root.val);//左边节点全部遍历完之后在取节点的值
        nums.addAll(inorderTraversal(root.right));
    }
    return nums;
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> nums = new ArrayList<>();
    if(root == null){
        return nums;
    }else{
        nums.addAll(postorderTraversal(root.left));
        nums.addAll(postorderTraversal(root.right));
        nums.add(root.val);//左右节点有取到值之后再获取本身节点值
    }
    return nums;
}