【刷算法】求二叉树深度的递归以及非递归解法

Carl 发布于2019-08-22 18:13 / 1664人阅读

摘要：题目描述输入一棵二叉树，求该树的深度。递归解法非递归解法原来标识当前层是否遍历完毕当前弹出元素为时，说明一层以及遍历完毕了，所以最后一层的弹出时不能再往队列里面加了

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

递归解法

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Depth(r) {
    if(r === null)
        return  0;
    return Math.max(Depth(r.left), Depth(r.right))+1;
}

非递归解法

function TreeDepth(r)
{
    if(r === null)
        return 0;
    var q = [];
    var depth = 0;
    q.push(r);
    // null原来标识当前层是否遍历完毕
    q.push(null);
    
    while(q.length !== 0){
        var cur = q.shift();
        // 当前弹出元素为null时，说明一层以及遍历完毕了，所以depth+1
        if(cur === null){
            depth++;
            if(q.length!==0)
                // 最后一层的null弹出时不能再往队列里面加null了
                q.push(null);
        } 
        else{
            if(cur.left !== null)
                q.push(cur.left);
            if(cur.right !== null)
                q.push(cur.right);
        }
    }
    
    return depth;
}

云服务器 GPU云服务器非递归二叉树遍历最小二乘的递归算法非递归遍历二叉树算法

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

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

二叉树那些事儿

摘要：大家在聊到二叉树的时候，总会离不开链表。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。存储结构线性表主要由顺序表示或链式表示。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。大家在聊到二叉树的时候，总会离不开链表。这里先带大家一起了解一些基本概念。线性表概念线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关...

Little_XM 2019-08-22 16:28 评论0 收藏0
我的面试准备过程--二叉树(更新中)

摘要：写在最前面导师贪腐出逃美国，两年未归，可怜了我。拿了小米和美团的，要被延期，失效，工作重新找。把准备过程纪录下来，共勉。写在最前面导师贪腐出逃美国，两年未归，可怜了我。拿了小米和美团的offer，要被延期，offer失效，工作重新找。把准备过程纪录下来，共勉。二叉树的基础结点定义 public class TreeNode{ int val; TreeNode ...

Amio 2019-08-16 10:36 评论0 收藏0
【刷算法】翻转二叉树的递归和非递归解法

摘要：题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述解题思路递归版本首先，对数据结构比较了解的话会想到用递归来解决。所谓递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法来自维基百科。题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 评论0 收藏0
Javacript二叉树常见算法实现及快速排序求第K大值

摘要：后面也写了几种常见的排序算法，并用快排求第大值，另外如果之前版的作者看到的话可以留言，我会标明文章引用。之前实习笔试的时候刷题一直用的java，也参考某篇文章写过java版的二叉树常见算法，因为马上要转正面试了，这几天都在准备面试，就把之前的翻出来用javascript重新写了一遍，二叉树基本都是递归处理的，也比较简单，就当做热身。后面也写了几种常见的排序算法，并用快排求第K大值，另...

leeon 2019-08-26 12:15 评论0 收藏0