详解二叉树，计算二叉树的深度

2023-10-18 18:08| 来源: 网络整理| 查看: 265

这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战

背景

学习前端三个月了，准备刷刷面试题，总结总结，一天几道面试题，向大厂进军。

问题二叉树的深度

计算二叉树的深度

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

例如：

给定二叉树[3,9,20,null,null,15,7]

必备概念树

树：不包含回路的连通的无向图（树是一种简单的非线性结构）

树有着不包含回路这个特点，所以树就有很多特性：

一棵树中任意两个节点有且仅有唯一的一条路径连通。一棵树如果有N个节点，那它一定恰好有n-1条边。在一棵树中加一条边将会构成一条回路。树中有且仅有一个没有前驱的节点称为根节点。

二叉树

二叉树是一种非线性结构，二叉树是递归定义的，其结点有左右子树之分

特点：

1、每个结点最多有两颗子树

2、左子树和右子树是有顺序的，次序不能颠倒

3、即使某结点只有一个子树，也要区分左右子树

4、二叉树可为空，空的二叉树没有结点，非空二叉树有且仅有一个根节点

二叉树中有两种特殊的二叉树：满二叉树（每个节点左右两个节点都完整）、完全二叉树（除最后一层节点，其余的节点都达到最大值，最有一层节点只缺少右边的若干节点）

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉树的遍历（前序/中序/后序遍历）

前序遍历：首先访问根节点，然后遍历左子树，最后是右子树。（根->左->右）

中序遍历：首先遍历左子树，然后访问根节点，最后是右子树。（左->根->右）

后序遍历：首先遍历左子树，然后遍历右子树，最后是根节点。（左->右->根）

树的遍历总体分为两类深度优先遍历（DFS）:先序遍历，中序遍历，后序遍历广度优先遍历（BFS）:层序遍历（按层遍历）解析

我们了解的上述的遍历方式后，再分析这道题，求二叉树的深度？

1.求出左边树的最大深度

2.求出右边树的最大深度

3.最后加上根节点

这种思想正好是后序遍历。

代码:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if(root==null) return 0; //递归，先算左边，左边递归，每一个层级+1 //递归右边，每一层级+1 //求最大深度，最后加根节点 return Math.max(maxDepth(root.left),maxDepth(root.right))+1; };

验证：

结语

一步一步慢慢来，踏踏实实把活干！

【本文地址】

公司简介

联系我们