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);
    }
}

---

题解

思路：同样使用栈，按照对应的遍历方式来将所有的节点存储，接着来进行依次出栈取值，这里比较细节的一点就是要出栈取值的节点后会跟随这一个null值用于进行标识。

前序遍历

//统一迭代：前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放
    List<Integer> result = new ArrayList<>();
    if(root != null){
        stack.push(root);
    }
    while(!stack.isEmpty()){
        TreeNode node = stack.peek();
        if(node != null){
            stack.pop();
            //前序遍历：在栈中存储方式为右-左-中
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
            //null则为之后记录遍历值时的标识
            stack.push(node);
            stack.push(null);
        }else{
            stack.pop();//先将null标识弹出，之后直接来统计拿到值
            TreeNode valNode = stack.pop();
            result.add(valNode.val);
        }
    }
    return result;
}

---

中序遍历

//统一迭代：中序遍历
public List<Integer> postorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放
    List<Integer> result = new ArrayList<>();
    if(root != null){
        stack.push(root);
    }
    while(!stack.isEmpty()){
        TreeNode node = stack.peek();
        if(node != null){
            stack.pop();
            //中序遍历：在栈中存储方式为右-中-左
            if(node.right != null){
                stack.push(node.right);
            }
            stack.push(node);
            stack.push(null);
            if(node.left != null){
                stack.push(node.left);
            }

        }else{
            stack.pop();//先将null标识弹出，之后直接来统计拿到值
            TreeNode valNode = stack.pop();
            result.add(valNode.val);
        }
    }
    return result;
}

---

后序遍历

//统一迭代：后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放
    List<Integer> result = new ArrayList<>();
    if(root != null){
        stack.push(root);
    }
    while(!stack.isEmpty()){
        TreeNode node = stack.peek();
        if(node != null){
            stack.pop();
            stack.push(node);
            stack.push(null);
            //中序遍历：在栈中存储方式为右-中-左
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }

        }else{
            stack.pop();//先将null标识弹出，之后直接来统计拿到值
            TreeNode valNode = stack.pop();
            result.add(valNode.val);
        }
    }
    return result;
}

---

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

整理者：长路 时间：2021.11.7