144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

输入：root = [1,null,2,3] 输出：[1,2,3]

1. 递归或者栈。空间O(n)。
2. 线索二叉树，当前节点左右子树不为空，则令当前节点左孩子的最右节点(当前节点的前驱)的右指针指向当前节点右孩子。注意在这里该最右节点指向的不一定是该节点的后继节点，但一定是其父亲节点前驱的后继节点。空间O(1)。

public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer> res=new ArrayList<>();
         if(root==null) return res;
         TreeNode p=root;
         while(p!=null)
         {
             if(p.right!=null&&p.left!=null)
             {
                 TreeNode pre=p.left;
                 while(pre.right!=null) pre=pre.right;
                 pre.right=p.right;
             }
             res.add(p.val);
             if(p.left!=null) p=p.left;
             else p=p.right;
         }
         return res;
    }