首页 > 其他分享 >二叉树的迭代遍历-栈

二叉树的迭代遍历-栈

时间:2023-08-14 15:55:47浏览次数:34  
标签:right 迭代 res 遍历 二叉树 root stack left

二叉树的迭代遍历-栈

二叉树的递归遍历书写简单,做题时能够帮助快速完成dfs

但是往往有某些面试官或者题目要求,使用迭代法完成树的遍历

作为复习材料,不导出推导过程,只给出核心记忆点

TreeNode

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

反序列化工具 BuildTree.toTree(String)

案例

/*
                   4
                 /   \
                2     6
               / \
              1   3
 */

前序遍历(根左右)

  1. 栈的入栈出栈方向是相反的
  2. 根节点遍历到就会记录到(从根节点推导出)

root出栈 -> root.right入栈 -> root.left入栈

/**
 * 前序遍历 - 根左右 - 迭代法
 * - 核心 入栈 根 右 左
 */
public class PreOrder {
    public static void main(String[] args) {
        String tree = "4,2,6,1,3,#,#,#,#,#,#";
        TreeNode root = BuildTree.toTree(tree);
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        ArrayList<Integer> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop(); // root
            res.add(curr.val);

            if (curr.right != null)      // right
                stack.push(curr.right);
            if (curr.left != null)       // left
                stack.push(curr.left);
        }
        System.out.println("PreOrder=" + res);
    }
}

// PreOrder=[4, 2, 1, 3, 6]

后序遍历(左右根)

前序遍历给出的核心入栈出栈操作是:root出栈 -> root.right入栈 -> root.left入栈

对应前序遍历的实际记录顺序是:root -> left -> right

不难看出,left, right 的入栈顺序与实际记录顺序相反,因此如果:

root出栈 -> root.left入栈 -> root.right入栈

那么得到的记录顺序是:root -> right -> left

将记录取反获得:left -> right -> root 为后序遍历顺序

/**
 * 后序遍历 - 左右根 - 迭代法
 * - 核心 入栈 根 左 右(才前序遍历推导得出), 结果取反
 */
public class PostOrder {
    public static void main(String[] args) {
        String tree = "4,2,6,1,3,#,#,#,#,#,#";
        TreeNode root = BuildTree.toTree(tree);
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        ArrayList<Integer> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            res.add(curr.val);

            if (curr.left != null)
                stack.push(curr.left);
            if (curr.right != null)
                stack.push(curr.right);
        }
        int l = 0, r = res.size() - 1;
        while (l < r) {
            int ll = res.get(l);
            int rr = res.get(r);
            res.set(l, rr);
            res.set(r, ll);
            l++;
            r--;
        }
        System.out.println("PostOrder=" + res);
    }
}

// PostOrder=[1, 3, 2, 6, 4]

中序遍历(左根右)

访问顺序和记录顺序不一致,单独讨论

中序遍历总是记录每一个节点的左子树后,记录当前节点,再记录右子树

/**
 * 中序遍历 - 左根右 - 迭代法
 * - 核心 不断将当前节点的左节点入栈, 直到当前节点为null, 弹出后逐个处理右节点
 */
public class InOrder {
    public static void main(String[] args) {
        String tree = "4,2,6,1,3,#,#,#,#,#,#";
        TreeNode root = BuildTree.toTree(tree);
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        ArrayList<Integer> res = new ArrayList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        System.out.println("InOrder" + res);
    }
}

// InOrder[1, 2, 3, 4, 6]

标签:right,迭代,res,遍历,二叉树,root,stack,left
From: https://www.cnblogs.com/jentreywang/p/17628874.html

相关文章

  • 二叉树的层次遍历
    #include<stdio.h>#include<stdlib.h>#defineMaxSize100typedefstructTreeNode{ intdata; structTreeNode*lchild,*rchild;}TreeNode,*Tree;typedefstruct{ TreeNode*data[MaxSize]; intfront; intrear;}Queue;voidInitQueue(Queue......
  • 二叉树的非递归遍历
    //非递归操作#include<stdio.h>#include<stdlib.h>#defineMaxSize200typedefstructTreeNode{intdata;structTreeNode*lchild,*rchild;}TreeNode,*Tree;typedefstruct{Treedata[MaxSize];inttop;}Stack;voidInitStack(S......
  • 二叉树的递归遍历
    #include<stdio.h>#include<stdlib.h>typedefstructTNode{intdata;structTNode*lchild,*rchild;}TreeNode,*Tree;/*在这段代码中,递归函数`CreateTree`在执行`return`语句后,会立即返回到调用它的上一层递归调用。但是,整个递归过程并没有结束,仍然会......
  • P9534 [YsOI2023] 广度优先遍历
    好题。首先考虑到对于任意的边的输入顺序,分层图是不会变的,即所有点到根的最短距离不变。那么分为两种边,分别为不同层的边相连,相同层的边相连。显然第二种边是无用的,我们将其放到最后输出即可。由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案,所以我们按......
  • import.meta.globEager('./src/components/**/*.vue'); 遍历文件
    main.jsconstimportAll=(modules)=>{Object.keys(modules).forEach((key)=>{constcomponent=key.replace('/src/','@/').replace('.vue','');constcomponentName=key.split('/').slice......
  • 二叉树的层序遍历
    intfindBottomLeftValue(TreeNode*root){queue<TreeNode*>qu;if(root!=nullptr)qu.push(root);intsize=0;intresult=0;while(!qu.empty()){TreeNode*temp;size=qu.size();......
  • 一次项目迭代的回顾
    最近一个迭代接了一个需求,自己提了一个需求总的来说,做的一般般,核心问题在于工作量的预估跟实际的工作量差别较大,导致开发质量一般,自测质量一般,最后上线质量也一般请求录制和录制布局需求即使把改动的技术点整理了出来,但没有做好的点也很多技术点整理的太粗糙,没有暴露细节例......
  • [代码随想录]Day16-二叉树part05
    题目:513.找树左下角的值思路:层序遍历是最好的选择了,先放右节点,再放左节点最后一个元素就是最左侧的节点。说白了层序遍历就是广度优先搜索BFS。代码:funcfindBottomLeftValue(root*TreeNode)int{node:=rootq:=[]*TreeNode{root}forlen(q)>0{......
  • 3.0 Python 迭代器与生成器
    当我们需要处理一个大量的数据集合时,一次性将其全部读入内存并处理可能会导致内存溢出。此时,我们可以采用迭代器Iterator和生成器Generator的方法,逐个地处理数据,从而避免内存溢出的问题。迭代器是一个可以逐个访问元素的对象,它实现了python的迭代协议,即实现了__iter__()和__next_......
  • 3.0 Python 迭代器与生成器
    当我们需要处理一个大量的数据集合时,一次性将其全部读入内存并处理可能会导致内存溢出。此时,我们可以采用迭代器Iterator和生成器Generator的方法,逐个地处理数据,从而避免内存溢出的问题。迭代器是一个可以逐个访问元素的对象,它实现了python的迭代协议,即实现了__iter__()和__next__......