[数据结构与算法]力扣题144前序遍历/题145后序遍历

144.前序遍历

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

示例 1：

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

输出：[1,2,3]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

示例 4：

输入：root = [1,2]

输出：[1,2]

示例 5：

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

输出：[1,2]

1.递归方法。用一个栈来存储遍历到的节点。前序遍历的顺序是根---左---右。

/**
 * Definition for a binary tree node.
 * public 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 List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();//创建存储前序遍历的结果
        
        if(root == null){//树为null，直接返回
            return list;
        }

        Deque<Integer> stack = new LinkedList<>();//用一个栈来存储当前遍历到的节点
        preorder(root,list,stack);
        return list;
    }
    //根左右的顺序
    public void preorder(TreeNode node,List<Integer> list,Deque<Integer> stack){
        stack.push(node.val);//先将当前根节点加入栈

        list.add(stack.peek());//将当前根节点的值加入list
        stack.pop();//取出遍历过的节点

        if(node.left != null){//如果存在左子树，继续遍历左子树
            preorder(node.left,list,stack);
        }

        if(node.right != null){//如果存在右子树，继续遍历右子树
            preorder(node.right,list,stack);
        }
    }
}

? ?答案的递归写法：不需要辅助空间栈。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

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

2.迭代。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();//创建存储前序遍历的结果

        Deque<TreeNode> stack = new LinkedList<>();//用一个栈来存储当前遍历到的节点
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){//先遍历左子树，一直到左子树不存在
                stack.push(node);//先将没个左子树的根节点加入队列
                list.add(node.val);
                node = node.left;
            }

            node = stack.pop();//取出当前的根节点
            node = node.right;//再去找右子树
        }
        return list;
    }
}

题源：力扣

145.后序遍历

1.递归：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        postorder(root,list);
        return list;
    }
    //左、右、根
    public void postorder(TreeNode node,List<Integer> list){
        if(node == null){
            return;
        }

        if(node.left != null){
            postorder(node.left,list);
        }

        if(node.right != null){
            postorder(node.right,list);
        }

        list.add(node.val);
    }
}

2.迭代。注意后序遍历的迭代，因为左子树、右子树遍历完后都要回到根节点，因此需要记录一个前一次遍历的节点，来判断对于当前节点来说，其右子树是否被遍历过。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;//当前节点
        TreeNode pre = null;//前一个节点

        while(node != null || !stack.isEmpty()){
            while(node != null){//存在左子树，先把左子树的全部根节点加入栈
                stack.push(node);
                node = node.left;
            }

            node = stack.peek();//取出左子树的最后一个根节点
            
            //如果此时该节点没有右子节点即为叶子节点，则加入list；
            //或者当前节点的右子节点是上一个遍历过的节点，则该根节点的右子树已经遍历完毕，也将当前根节点加入list
            if(node.right == null || node.right == pre){
                list.add(node.val);
                stack.pop();
                pre = node;
                node = null;
            }else{//存在右子树，且右子树未被遍历过
                node = node.right;
            }
        }
        return list;
    }
}

题源：力扣