剑指offer——层序遍历+双端队列

小咪咪 2022-11-14 11:55 105阅读 0赞

![转自leetcode剑指offer][leetcode_offer]层序遍历的变式，用双端队列来实现偶数行从左到右，奇数行从右到左（索引从0开始），代码如下：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public List<List<Integer>> levelOrder(TreeNode root) { 
            List<List<Integer>> res=new ArrayList<>();
            Queue<TreeNode> queue=new LinkedList<>();
            if(root!=null) queue.add(root);
            while(!queue.isEmpty()){ 
                LinkedList<Integer> tempList=new LinkedList<>();
                for(int i=queue.size();i>0;i--){ 
                    TreeNode node=queue.poll();
                    if(res.size()%2==0) tempList.addLast(node.val);
                    else tempList.addFirst(node.val);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                }
                res.add(tempList);
            }
            return res;
        }
    }

[leetcode_offer]: /images/20221022/7a7d735d41c64c8d9932cfcd57ddb4ce.png

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】之层次遍历

题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。思路：层次遍历树，说到数组的根节点和左右子节点的关系，每个第i个节点，他的第2i和2i+1就是他们的子

小鱼儿/ 2023年06月24日 10:28/ 0 赞/ 35 阅读

相关层序遍历非队列方法

不使用队列，实现层序遍历 import static java.lang.Integer.max; public class LayerOrderL

朱雀/ 2022年11月27日 07:19/ 0 赞/ 124 阅读

相关剑指offer——层序遍历+双端队列

![转自leetcode剑指offer][leetcode_offer]层序遍历的变式，用双端队列来实现偶数行从左到右，奇数行从右到左（索引从0开始），代码如下： /

小咪咪/ 2022年11月14日 11:55/ 0 赞/ 106 阅读

相关剑指offer：重建二叉树（根据前序遍历和中序遍历结果）

![转自leetcode剑指offer][leetcode_offer]根据前序遍历和中序遍历的结果构造二叉树，思路（leetcode上有图文详解）：由前序遍历结果得到根节点的

ゝ一纸荒年。/ 2022年11月12日 02:33/ 0 赞/ 242 阅读

相关【剑指offer】先序、中序遍历结果重建二叉树

题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\

小鱼儿/ 2022年07月12日 02:57/ 0 赞/ 212 阅读

相关【剑指offer】先序、中序遍历结果重建二叉树

题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\

分手后的思念是犯贱/ 2022年07月12日 02:57/ 0 赞/ 200 阅读

相关剑指Offer LevelTraversalTree 层序遍历二叉树

题目描述：从上往下打印二叉树的每个结点，同一层的结点按照从左到右的顺序打印。思路： 1.循环+队列每次扫描本层的所有节点放入队列再从队头读取一个节点继续遍历子节点

Love The Way You Lie/ 2022年06月10日 13:59/ 0 赞/ 149 阅读

相关【剑指offer】二叉搜索树的后序遍历

题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。二叉搜索树是左子树都

曾经终败给现在/ 2022年04月17日 05:47/ 0 赞/ 187 阅读

相关【剑指offer】二叉搜索树的后序遍历

二叉搜索树的后序遍历题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不

一时失言乱红尘/ 2022年04月01日 12:14/ 0 赞/ 221 阅读

相关【剑指offer】二叉搜索树的后序遍历

题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。【分析】理解后序遍

小灰灰/ 2022年01月22日 13:57/ 0 赞/ 214 阅读