摘要:题目描述输入一棵二叉树,求该树的深度。递归解法非递归解法原来标识当前层是否遍历完毕当前弹出元素为时,说明一层以及遍历完毕了,所以最后一层的弹出时不能再往队列里面加了
题目描述
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
递归解法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; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/95634.html
摘要:写在最前面导师贪腐出逃美国,两年未归,可怜了我。拿了小米和美团的,要被延期,失效,工作重新找。把准备过程纪录下来,共勉。 写在最前面 导师贪腐出逃美国,两年未归,可怜了我。拿了小米和美团的offer,要被延期,offer失效,工作重新找。把准备过程纪录下来,共勉。 二叉树的基础 结点定义 public class TreeNode{ int val; TreeNode ...
摘要:题目描述操作给定的二叉树,将其变翻转为源二叉树的镜像。输入描述解题思路递归版本首先,对数据结构比较了解的话会想到用递归来解决。所谓递归,在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法来自维基百科。 题目描述 操作给定的二叉树,将其变翻转为源二叉树的镜像。 输入描述: 1 1 / ...
摘要:后面也写了几种常见的排序算法,并用快排求第大值,另外如果之前版的作者看到的话可以留言,我会标明文章引用。 之前实习笔试的时候刷题一直用的java,也参考某篇文章写过java版的二叉树常见算法,因为马上要转正面试了,这几天都在准备面试,就把之前的翻出来用javascript重新写了一遍,二叉树基本都是递归处理的,也比较简单,就当做热身。后面也写了几种常见的排序算法,并用快排求第K大值,另...
阅读 2114·2023-04-26 03:06
阅读 3525·2023-04-26 01:51
阅读 2050·2021-11-24 09:38
阅读 2423·2021-11-17 17:00
阅读 2283·2021-09-28 09:36
阅读 920·2021-09-24 09:47
阅读 2565·2019-08-30 15:54
阅读 1531·2019-08-30 15:44