力扣（144.94）补9.4

144.二叉树的前序遍历

递归代码倒不难，但仔细想想为什么这样递归我又是一头雾水，为什么这样递归能实现前序遍历呢，递归的本质还是没懂。用栈实现递归我也没懂。。。真的超级无敌烧脑。

class Solution {

    public void preorder(TreeNode root,Listans){

        if(root==null)

        return ;

        ans.add(root.val);

        preorder(root.left,ans);

        preorder(root.right,ans);

    }

    public List preorderTraversal(TreeNode root) {

        List ans=new ArrayList();

        preorder(root,ans);

        return ans;

    }

}

以下是栈的解法，自己模拟一遍发现确实没啥问题，但是为什么代码这样写呢。。。

class Solution {

    public List preorderTraversal(TreeNode root) {

        List ans=new ArrayList<>();

        Stack stack=new Stack<>();

        if(root==null)

        return ans;

        stack.push(root);

        while(stack.isEmpty()==false){

            TreeNode node=stack.pop();

            ans.add(node.val);

            if(node.right!=null){

                stack.push(node.right);

            }

            if(node.left!=null){

                stack.push(node.left);

            }

        }

        return ans;

    }

}

94.二叉树的中序遍历

递归的解法就不放了，递归这东西，看了一眼会了，但仔细思考又发觉不会。中序遍历时栈的实现和前序和后序都不一样呢。

class Solution {
    public List inorderTraversal(TreeNode root) {
        Stack stack=new Stack<>();
        List ans=new ArrayList<>();
        if(root==null)
        return ans;
        TreeNode cur=new TreeNode();
        cur=root;
        while(stack.isEmpty()==false||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();
                ans.add(cur.val);
                cur=cur.right;
            }
        }
        return ans;
    }
}