算法问题——二叉树的三种遍历（递归和非递归问题）

144. 二叉树的前序遍历

/**
*非递归的方法
*/ 
public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();

        while(root != null || !stack.isEmpty()){
            while(root != null){
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            root = cur.right;
        }

        return res;
    }

/**
*递归的方式
*/
class Solution {
    public List preorderTraversal(TreeNode root) {
       List list = new ArrayList();
        if (root == null) {
            return list;
        }
        preorderTraversal1(root, list);
        return list;
    }
    public void preorderTraversal1(TreeNode root,List list) {
       //遍历根节点
        list.add(root.val);
       //遍历左子树
        if(root.left!=null){
            preorderTraversal1(root.left,list);
        }
       //遍历右子树
       if(root.right!=null){
           preorderTraversal1(root.right,list);
       }
    }
}

94. 二叉树的中序遍历

/**
*非递归的方式
*/
public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }

/*
*采用的是的递归的方法
*/
class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > list = new ArrayList < > ();
        helper(root, list);
        return list;
    }

    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}

145. 二叉树的后序遍历

/**
*非递归的方法
*/ 
public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new ArrayDeque();

        while(root != null || !stack.isEmpty()){
            while(root != null){
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode cur = stack.pop();
            root = cur.left;
        }

        Collections.reverse(res);
        return res;
    }

/**
*递归的方式
*/
class Solution {
    public List postorderTraversal(TreeNode root) {
        List list = new ArrayList();
        postorderTraversal(root, list);
        return list;
    }
    public void postorderTraversal(TreeNode root, List list) {
        //如果树为空的话
        if (root == null) {
            return;
        }
        //将左子树的放置
        if (root.left != null) {
            postorderTraversal(root.left, list);
        }
        //将右子树的放置
        if (root.right != null) {
            postorderTraversal(root.right, list);
        }
        //将当前子树的放置
        list.add(root.val);
    }
}