当前位置:网站首页>刷题笔记(十三)--二叉树:前中后序遍历(复习)

刷题笔记(十三)--二叉树:前中后序遍历(复习)

2022-06-11 11:34:00 梦想成为光头强!

系列文章目录

刷题笔记(一)–数组类型:二分法
刷题笔记(二)–数组类型:双指针法
刷题笔记(三)–数组类型:滑动窗口
刷题笔记(四)–数组类型:模拟
刷题笔记(五)–链表类型:基础题目以及操作
刷题笔记(六)–哈希表:基础题目和思想
刷题笔记(七)–字符串:经典题目
刷题笔记(八)–双指针:两数之和以及延伸
刷题笔记(九)–字符串: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;
    }
}

原网站

版权声明
本文为[梦想成为光头强!]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_53860901/article/details/125029389