刷题笔记（十三）--二叉树：前中后序遍历（复习）

系列文章目录

刷题笔记（一）–数组类型：二分法
刷题笔记（二）–数组类型：双指针法
刷题笔记（三）–数组类型：滑动窗口
刷题笔记（四）–数组类型：模拟
刷题笔记（五）–链表类型：基础题目以及操作
刷题笔记（六）–哈希表：基础题目和思想
刷题笔记（七）–字符串：经典题目
刷题笔记（八）–双指针：两数之和以及延伸
刷题笔记（九）–字符串：KMP算法
刷题笔记（十）–栈和队列：基础题目
刷题笔记（十一）–栈和队列：Top-K问题
刷题笔记（十二）–复习：排序算法

题录

144. 二叉树的前序遍历

题目链接如下：

144. 二叉树的前序遍历

题目截屏如下：

解法如下：

递归写法

public class 前序遍历 {
    
    public List<Integer> preorderTraversal(TreeNode root) {
    
        //构造一个List用来返回
        List<Integer> list = new ArrayList<>();
        //然后开始前序遍历
        preorderTraversal(list,root);
        return list;
    }

    public void preorderTraversal(List<Integer> list,TreeNode root){
    
        //如果为空就直接返回
        if(root == null){
    
            return;
        }
        //前序遍历：根节点 --> 左子树 --> 右子树
        list.add(root.val);
        preorderTraversal(list,root.left);
        preorderTraversal(list,root.right);
    }
}

迭代写法

public List<Integer> preorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();//构造一个list用来接收root值
        Stack<TreeNode> stack = new Stack<>();//构造一个栈用来前序遍历
        //不为空就把root入栈
        if(root != null){
    
            stack.push(root);
        }
        //栈不为空就开始遍历
        while(!stack.isEmpty()){
    
            TreeNode node = stack.pop();
            list.add(node.val);
            //栈的特性：先进后出，所以右子树先入栈后出
            if(node.right != null){
    
                stack.push(node.right);
            }
            //左子树后入栈先出
            if(node.left != null){
    
                stack.push(node.left);
            }
        }
        return list;
    }

94. 二叉树的中序遍历

题目链接如下：

94. 二叉树的中序遍历

题目截图如下：

递归写法

递归写法和上面的差不多，就是调换了一下位置

public class 中序遍历_递归写法 {
    
    public List<Integer> inorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        inorderTraversal(list,root);
        return list;
    }

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

迭代写法

public class 中序遍历_迭代写法 {
    
    public List<Integer> inorderTraversal(TreeNode root) {
    
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        //栈为空并且cur == null的时候就遍历完毕
        while(!stack.isEmpty() || cur != null){
    
            //首先就是往左走，一直往左走，走到没有地方走为止
            if(cur != null){
    
                stack.push(cur);
                cur = cur.left;
            }else{
    //如果说左子树为null的时候，就把当前节点值加入，然后遍历右子树的左子树
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}

145. 二叉树的后序遍历

题目链接如下：

145. 二叉树的后序遍历

题目截屏如下：

递归写法

public class 后序遍历_递归 {
    
    public List<Integer> postorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        postorderTraversal(list,root);
        return list;
    }

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

迭代写法–1

这里的话其实就是把前序遍历得到的list翻转一下

public class 后序遍历_迭代 {
    
    public List<Integer> postorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) {
    
            stack.push(root);
        }
        while(!stack.empty()){
    
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.left != null){
    
                stack.push(node.left);
            }
            if(node.right != null){
    
                stack.push(node.right);
            }
        }
        Collections.reverse(list);
        return list;
    }
}

迭代写法–2

public class 后续遍历_迭代2 {
    
    public List<Integer> postorderTraversal(TreeNode root) {
    
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // cur 用来遍历
        TreeNode cur = root;
        // prev 用来记录上次遍历的个结点
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
    
            if (cur != null) {
    
                stack.add(cur);
                cur = cur.left;
            } else {
    
                cur = stack.pop();
                if (cur.right != null && cur.right != prev) {
    
                    // 有右子树并且右子树没遍历，需放回根结点到栈中
                    stack.push(cur);
                    // 接下来遍历右子树
                    cur = cur.right;
                } else {
    
                    // 没有右子树，或者右子树被遍历过，
                    res.add(cur.val);
                    // 更新前指针
                    prev = cur;
                    // 以该结点的子树都已遍历，下次需要从栈中取父亲结点向上遍历，所以 cur == null
                    cur = null;
                }
            }
        }
        return res;
    }
}