二叉树的“查”
2022/4/17 23:18:23
本文主要是介绍二叉树的“查”,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言:今天来重点讲一下二叉树的“查”,二叉树也是一种数据存储方式,类比于数组来说,最基本的“查”应该有以下几种:
- 二叉树的大小即节点个数
- 二叉树的最大深度和最小深度
- 二叉树的最近公共祖先
方法论:
本文中主要用到了两种思维模式,如下:
- 是否遍历一遍二叉树就可以得到结果,如果可以,只需要对二叉树的递归遍历方式或者迭代遍历方式便可以可到结果,这种思维模式称为
遍历
思维模式 - 是否需要借助子树的返回值?如果需要可以定义一个递归函数求解(注重逻辑的自洽),这种思维模式下:
递归函数需要返回值
,代码通常写在后序位置
,这种思维模式称为分治
思维模式。
无论那种思维模式,你都需要思考:
如果单独抽出一个节点,他需要做什么事情,需要在前序、中序、后序哪个位置做事情?不同位置的代码仅能接收到该代码之前的结果,前序位置的代码自然接收不到子树的消息,因为前序代码执行的时候,二叉树还没有开始遍历。
一、二叉树的节点个数
1. 普通二叉树的节点个数
1.1 遍历的思维模式
- 递归方式
class Solution { int count = 0; public int countNodes(TreeNode root) { if(root == null) return 0; count(root); return count; } void count(TreeNode root) { if(root == null) return; count(root.left); count(root.right); count++;//count++的位置在前、中、后序都可以放置,本质就是数组中的循环体中的count++ } }
- 迭代方式
迭代方式,深度迭代和广度迭代都可以,只需要将迭代代码中的result.add(curNode.val)改为count++即可,具体代码可参考我的上一篇文章二叉树遍历。
1.2 分治的思维模式
首先思考:如果你是一个树节点,你如何知道以你为父节点的二叉树节点个数?你的子树需要给你返回什么?
我的思考:二叉树的节点个数 = 父节点 + 左子树节点个数 + 右子树节点大小
class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; return 1 + countNodes(root.left) + countNodes(root.right); } }
2. 完全二叉树的节点个数
说完普通二叉树的节点个数,其实完全二叉树、满二叉树的节点个数也可以求,但是没有利用完全二叉树和满二叉树的性质,去提高减少代码的时间复杂度和空间复杂度。
既然要利用完全二叉树的性质,那就需要知道他的性质是什么:
- 完全二叉树的子树必定可以分解为多个满二叉树,这里的子树也可以是子树的子树,单个节点也可以是满二叉树。
- 满二叉树的节点个数: 2^h-1,这里的h是层数。root节点为第一层。
知道了以上的性质,我们就不需要遍历左右子树,只需要知道满二叉子树的高度即可。
class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int hl = 1; int hr = 1;//考虑极端情况,root.left == null或者root.right == null; TreeNode left = root.left; TreeNode right = root.right; while(left != null) { left = left.left; hl++; } while(right != null) { right = right.right; hr++; } if(hl == hr) return (2<<(hl-1)) - 1;//如果是满二叉树,按照2^h-1计算,2<<1等于2^2; //如果不是满二叉树,按照普通二叉树计算 return 1 + countNodes(root.left) + countNodes(root.right); } }
3. 满二叉树的节点个数
class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int h = 0;//考虑极端情况,root.left == null&&root.right == null; while(root != null) { root = root.left; h++; } return (2<<(h-1)) - 1; } }
关于完全二叉树和满二叉树求深度h的代码总结:
明确一下几点:
1、root节点是谁?是root还是root.left还是root.right,即你所求二叉树的root节点是谁?
2、二叉树的h从0还是从1开始,我觉得这里的h代表的是所求二叉树的父节点层数-1
,为什么减去1,是因为紧接着下面h++
,这也就意味着只要你的root != null,就会+1
。
二、二叉树的最大深度和最小深度
1. 二叉树的最大深度
1.1 遍历的思维模式
- 递归方式
- 一遍遍历是否可以得到结果?可以,可以维护一个全局变量用来记录深度。
- 记录什么的深度?自然是每个叶子节点的深度,然后取深度的最大值就是二叉树的最大深度。
- 站在一个树节点的角度,深度该如何计算?进入节点的时候深度加1,离开节点的时候深度减1。
class Solution { int depth = 0;//当前叶子结点深度 int max = 0;//全局最大深度 public int maxDepth(TreeNode root) { traverse(root); return max; } void traverse(TreeNode root) {// if(root == null) { max = Math.max(depth,max); return; } depth++;//进入节点,深度+1 traverse(root.left); traverse(root.right); depth--;//离开节点,深度-1 } }
- 迭代方式
采用层序迭代的方式用来计算二叉树的最大深度最方便,因为层序迭代代码的内部会维护当前队列的大小,以一层为一个循环,仅需要维护一个全局变量depth,每次循环后加1便可以计算出二叉树的最大深度。
class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0;//维护全局深度变量,初始为层数-1,即1-1=0; while(!queue.isEmpty()) { int n = queue.size(); for(int i=0; i<n; i++) { TreeNode curNode = queue.poll(); if(curNode.left != null) queue.offer(curNode.left); if(curNode.right != null) queue.offer(curNode.right); } depth++; } return depth; } }
只要涉及到深度相关的问题,要着重考虑初始深度h的取值,考虑极端情况去对h取值。
1.2 分治的思维模式
首先思考:如果你是一个树节点,你如何知道以你为父节点的二叉树深度?你的子树需要给你返回什么?
我的思考:二叉树的最大深度 = 父节点深度 + 左右子树深度的最大值
class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; return 1 + Math.max(maxDepth(root.left),maxDepth(root.right)); } }
2. 二叉树的最小深度[重点复习
这篇关于二叉树的“查”的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南