【刷算法】按照之字形打印二叉树

phpmatt 发布于2019-08-22 18:46 / 1486人阅读

摘要：题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推分析第一反应可以按照普通的层次遍历然后再把第等等偶数层的结果翻转一下，但是那样子效率太低。

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

分析

第一反应可以按照普通的层次遍历然后再把第2、4、6等等偶数层的结果翻转一下，但是那样子效率太低。

上网查阅可以使用双向队列，即两头都可以进和出。需要从左到右打印的从队列头部进入和弹出，需要从右往左打印的从队列尾部进入和弹出

代码实现

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */


function Print(r)
{
    if(r === null)
        return [];
    var ds = [];
    var dir = "r";
    var res = [];
    
    ds.unshift(null);
    ds.unshift(r);
    
    while(ds.length > 1) {
        var temp = [];
        if(dir === "r"){
            var cur = ds.shift();
            while(cur !== null) {
                temp.push(cur.val);
                if(cur.left !== null)
                    ds.push(cur.left);
                if(cur.right !== null)
                    ds.push(cur.right)
                cur = ds.shift();
            }
            ds.unshift(null);
        }else{
            var cur = ds.pop();
            while(cur !== null){
                temp.push(cur.val);
                if(cur.right !== null)
                    ds.unshift(cur.right);
                if(cur.left !== null)
                    ds.unshift(cur.left);
                cur = ds.pop();
            }
            ds.push(null);
        }
        
        res.push(temp);
        dir = dir === "r" ? "l" : "r";
    }
    
    return res;
}

module.exports = {
    Print : Print
};

云服务器 GPU云服务器二叉树算法最优二叉树算法图之字形二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96178.html

【刷算法】从上往下打印二叉树

摘要：题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。分析二叉树的层次遍历，可以借助队列的帮助实现题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。分析二叉树的层次遍历，可以借助队列的帮助实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right =...

ShowerSun 2019-08-22 18:20 评论0 收藏0
【递归+迭代详解】二叉树的morris遍历、层序遍历、前序遍历、中序遍历、后序遍历

摘要：递归解法由于层次遍历的递归解法不是主流，因此只介绍前三种的递归解法前序遍历递归递归中序遍历递归递归后序遍历递归递归三种递归遍历的总结递归终止的条件为碰到空节点。目录分析二叉树的前序，中序，后序的遍历步骤 1.层序遍历方法一：广度优先搜索 (以下解释来自leetcode官方题解) 方法...

niceforbear 2021-11-16 11:45 评论0 收藏0
【刷算法】二叉树中和为某一值的路径

摘要：题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用递归来解决，本题亦如此。题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用...

zxhaaa 2019-08-22 18:21 评论0 收藏0
【刷算法】层次遍历二叉树

摘要：题目从上到下按层打印二叉树，同一层结点从左至右输出。分析分层次遍历肯定要使用队列来完成了，没啥好分析的代码实现题目从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。分析分层次遍历肯定要使用队列来完成了，没啥好分析的代码实现 /* function TreeNode(x) { this.val = x; this.left = null; ...

feng409 2019-08-22 18:46 评论0 收藏0