leetcode【二叉树—简单】二叉树迭代遍历

文章目录

• 前言
• 题目
• 题解
• 前序遍历
• 中序遍历
• 后序遍历

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为二叉树专题。

---

题目

题目来源leetcode

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

本地调试代码：

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 static void main(String[] args) {
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, node5);
        TreeNode node2 = new TreeNode(2, node4, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node1 = new TreeNode(1, node2, node3);
        morrisPre(node1);
    }
}

---

题解

前序遍历

144. 二叉树的前序遍历

思路：使用栈来进行前序遍历，每次出栈一个元素的操作都是一致的：先读取出栈的元素值，紧接着出栈节点的右节点先入栈，左节点后入栈。

• ps：入栈的节点不为null，先入右节点，后入左节点好处就是每次出栈得到的必是左节点的元素！

public List<Integer> preorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    List<Integer> nums = new ArrayList<>();
    if(root != null){
        stack.push(root);//先将头节点入栈
    }
    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        //从栈中读取节点的值(此时就会先读取到左节点的值，之后则是右节点的值)
        nums.add(node.val);
        //首先将节点的右节点入栈
        if(node.right != null){
            stack.push(node.right);
        }
        //接着将节点的左节点入栈
        if(node.left != null){
            stack.push(node.left);
        }
    }
    return nums;
}

---

中序遍历

94. 二叉树的中序遍历

思路：同样是用栈+指针的形式，指针用来寻路，栈中存储的都是待取值的一个个节点。若是当前节点为null，说明已经某个节点的左节点已经走完，走完的相同操作都是出栈一个元素，取到值之后开始继续对右节点进行探索。

//栈中存储的是多个待取值的节点
public List<Integer> inorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    List<Integer> nums = new ArrayList<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
        //若是节点不为空，则直接入栈
        if(cur != null){
            stack.push(cur);
            cur = cur.left;//继续对节点的左节点遍历
        }else{ //若是节点为空，表名左节点已经探索结束
            //从栈中取出一个元素
            cur = stack.pop();
            nums.add(cur.val);//存储值
            cur = cur.right;//开始对右节点进行相同操作
        }
    }
    return nums;
}

---

后序遍历

145. 二叉树的后序遍历

思路：与前序遍历方式相同，前序遍历是先出栈取值，接着入栈右节点、左节点；这里的话先取值，接着入栈左节点、右节点，最终将取到的值进行反转。(前序遍历方式：左-右-中，这里取值刚好反过来中-右-左，最终反转即可)

//后序遍历取法 左-右-中  入栈顺序：中-右-左  ，与前序迭代遍历很相似，出栈元素取值。最终我们反转一下取到的值就是后序遍历取值
public List<Integer> postorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    List<Integer> nums = new ArrayList<>();
    if(root != null){
        stack.push(root);
    }
    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        nums.add(node.val);
        if(node.left != null){
            stack.push(node.left);
        }
        if(node.right != null){
            stack.push(node.right);
        }
    }
    Collections.reverse(nums);
    return nums;
}

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.7