栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

目录
  • 系列文章目录
  • 题录
    • 144. 二叉树的前序遍历
      • 递归写法
      • 迭代写法
    • 94. 二叉树的中序遍历
      • 递归写法
      • 迭代写法
    • 145. 二叉树的后序遍历
      • 递归写法
      • 迭代写法--1
      • 迭代写法--2

系列文章目录

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

题录 144. 二叉树的前序遍历

题目链接如下:

144. 二叉树的前序遍历

题目截屏如下:

解法如下:

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

    public void preorderTraversal(List list,TreeNode root){
        //如果为空就直接返回
        if(root == null){
            return;
        }
        //前序遍历:根节点 --> 左子树 --> 右子树
        list.add(root.val);
        preorderTraversal(list,root.left);
        preorderTraversal(list,root.right);
    }
}
迭代写法
public List preorderTraversal(TreeNode root) {
        List list = new ArrayList<>();//构造一个list用来接收root值
        Stack 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 inorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        inorderTraversal(list,root);
        return list;
    }

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

迭代写法
public class 中序遍历_迭代写法 {
    public List inorderTraversal(TreeNode root) {
        Stack stack = new Stack<>();
        List 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 postorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        postorderTraversal(list,root);
        return list;
    }

    public void postorderTraversal(List 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 postorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        Stack 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 postorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        Stack 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;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936051.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号