赞
踩
- 在二叉树中,一个元素也称为一个结点。
- 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分,其次子树的次序不能颠倒,因此二叉树是有序树。
一般二叉树都是由以下四种形态的二叉树组合形成的
注意:
子树也必须是二叉树才能满足该树整体是一个二叉树
满二叉树: 一个二叉树,如果每一层的节点数都达到最大值,则这个二叉树就是满二叉树。
性质: 如果一个二叉树的层数是k,且节点数是 2k-1,则它就是满二叉树。
完全二叉树: 完全二叉树是效率很高的数据结构,它是由满二叉树引申出来的。它的叶子节点只会出现在最后2层,且最后一层的叶子节点都靠左对齐。 (满二叉树是一种特殊的完全二叉树)
- 若规定根节点的层数为1,则一棵非空二叉树的第 i 层上最多有 2i-1(i>0)个节点
- 若规定只有根节点的二叉树的深度为1,则深度为 k 的二叉树的最大节点数是 2k-1(k>=0)
- 对任何一棵二叉树,如果其叶子节点个数为 m,度为2的非叶子节点个数为 n,则有 m=n+1
- 具有 n 个节点的完全二叉树的深度为 log2(n+1) 向上取整
- 对于具有 n 个节点的完全二叉树,如果按照从上至下、从左至右的顺序对所有节点从0开始编号,则对序号为 i 的节点有:
* 若 i>0,双亲序号为:(i-1)/2
- 1
* 若 i=0,i 为根节点编号,无双亲节点
- 1
* 若 2i+1<n,左孩子序号为:2i+1,否则没有左孩子
- 1
* 若 2i+2<n,右孩子序号为:2i+2,否则没有右孩子
- 1
练习题:
假设一棵完全二叉树中总共有1000个节点,则该二叉树中有____个叶子节点,____个非叶子节点,____个节点只有左孩子,____个节点只有右孩子。
答案:
500、500、1、0
解析:
- 由于这是一个完全二叉树,所以不可能出现只有右孩子的节点,故最后一空为0
- 通过节点个数1000,可以推导出该树的深度为10
- 第10层节点数可以通过总节点数减去前9层节点数得到,为1000-511=489
- 叶子节点数=第10层的节点数+第九层度为0的节点数,而通过第10层的节点数可以知道他们的父节点有489/2+1=245
- 由于这是一个完全二叉树,所以第9层的节点肯定是满的,易得第9层节点数为256,而去除第九层度不为0的节点数,得到第九层叶子节点有256-245=11
- 故叶子节点数为489+11=500,非叶子节点数为1000-500=500
- 而完全二叉树的节点只有左子树的结果有1或0,通过第十层的节点数489为偶数,我们知道肯定有一个父节点只有一个孩子节点,即只有左子树的节点为1
二叉树的存储结构分为:顺序存储(在堆中介绍)和类似于链表的链式存储
二叉树的链式存储是通过一个一个的节点引用起来的,表示方法有:孩子表示法和孩子双亲表示法
孩子表示法:
class Node{
int val; // 数值域
Node left; // 左孩子的引用,常常代表以左孩子为根的整棵树
Node right; // 右孩子的引用,常常代表以右孩子为根的整棵树
}
孩子双亲表示法:
class Node{
int val; // 数值域
Node left; // 左孩子的引用,常常代表以左孩子为根的整棵树
Node right; // 右孩子的引用,常常代表以右孩子为根的整棵树
Node parent; // 当前节点的根节点
}
二叉树是一个非线性的数据结构,对它进行遍历的方式其实有多种,因此如果我们都以自己的方式去遍历二叉树,那么这个代码的易懂性就大大降低,显得很混乱。
为此对于二叉树,根据遍历根节点的先后次序,我们有以下三种遍历方式(N:代表根节点;L:代表根节点的左子树;R:代表根节点的右子树)
- 前序遍历(NLR): 先访问根节点➡根的左子树➡根的右子树
- 中序遍历(LNR): 先访问根的左子树➡根节点➡根的右子树
- 后序遍历(LRN): 先访问根的左子树➡根的右子树➡根节点
练习题:
请写出下面这棵二叉树的四种遍历方式
答案:
- 前序遍历:ABDEHCFG
- 中序遍历:DBEHAFCG
- 后序遍历:DHEBFGCA
注意:
不管是前序、中序还是后序遍历,遍历的路径是一样的,但访问的方式是不一样的
除了前中后序遍历外,二叉树还有一种很直观的遍历方式:层序遍历。层序遍历就是从二叉树的根节点出发,首先访问该树的第一层的根节点,然后从左到右访问第二层的节点,接着是第三层的节点,以此类推。
对于上图的树,使用层序遍历,节点被访问的顺序为:ABCDEFGH
层序遍历一般使用非递归的方式,具体的实现方法可以使用队列。
代码: 实现层序遍历
public void levelOrderTraversal(Node root){
if(root==null){
return;
}
Queue queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node node=queue.poll();
System.out.print(node.val+" ");
if(node.left!=null) {
queue.offer(node.left);
}
if(node.right!=null) {
queue.offer(node.right);
}
}
}
相关习题:
代码:
public List leftMap(Node root) {
List ret=new ArrayList<>();
if(root==null){
return ret;
}
Queue queue =new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
int count=size;
while(size>0){
Node top=queue.poll();
if(count==size){
ret.add(top.val);
}
if(top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
size–;
}
}
return ret;
}
代码:
public int maxWidth(Node root) {
if(root==null){
return 0;
}
Queue queue =new LinkedList<>();
queue.offer(root);
int max=0;
while(!queue.isEmpty()){
int size=queue.size();
max=Math.max(max,size);
while(size>0){
Node top=queue.poll();
if(top.left!=null){
queue.offer(top.left);
}
if(top.right!=null){
queue.offer(top.right);
}
size–;
}
}
return max;
}
代码:
public boolean isCompleteTree(Node root){
if(root==null){
return true;
}
Queue queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node top=queue.poll();
if(top==null){
break;
}
queue.offer(top.left);
queue.offer(top.right);
}
while(!queue.isEmpty()){
Node top=queue.peek();
if(top!=null){
return false;
}
queue.poll();
}
return true;
}
由于二叉树的创建一般使用递归,而递归创建二叉树将在后面重点介绍。故这里使用穷举法来创建下面这棵二叉树
实现代码:
class Node{
public char val;
public Node left;
public Node right;
public Node(char val){
this.val=val;
}
}
public class TestBinaryTree {
// 使用穷举的方式创建一棵二叉树
public Node createTree(){
Node A=new Node(‘A’);
Node B=new Node(‘B’);
Node C=new Node(‘C’);
Node D=new Node(‘D’);
Node E=new Node(‘E’);
Node F=new Node(‘F’);
Node G=new Node(‘G’);
Node H=new Node(‘H’);
A.left=B;
A.right=C;
B.left=D;
B.right=E;
E.right=H;
C.left=F;
C.right=G;
return A;
}
// 前序遍历
public void preOrderTraversal(Node root){
if(root==null) {
return;
}
System.out.print(root.val+" ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
// 中序遍历
public void inOrderTraversal(Node root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val+" ");
inOrderTraversal(root.right);
}
// 后序遍历
public void posOrderTraversal(Node root){
if(root==null){
return;
}
posOrderTraversal(root.left);
posOrderTraversal(root.right);
System.out.print(root.val+" ");
}
// 遍历思路-求节点个数
public static int size=0;
public void getSize1(Node root){
if(root==null){
return;
}
size++;
getSize1(root.left);
getSize1(root.right);
}
// 子问题思路-求节点个数
public int getSize2(Node root){
if(root==null){
return size;
}
int val=1+getSize2(root.left)+getSize2(root.right);
return val;
}
// 遍历思路-求叶子节点个数
public static int leafSize;
public void getLeafSize1(Node root){
if(root==null){
return;
}
if(root.leftnull&&root.rightnull){
leafSize++;
return;
}
getLeafSize1(root.left);
getLeafSize1(root.right);
}
// 子问题思路-求叶子节点个数
public int getLeafSize2(Node root){
if(root==null){
return 0;
}
if(root.leftnull&&root.rightnull) {
return 1;
}
int val=getLeafSize2(root.left)+getLeafSize2(root.right);
return val;
}
// 第 k 层的节点个数
public int getKLeafSize(Node root,int k){
if(root==null){
return 0;
}
if(k==1){
return 1;
}
int val=getKLeafSize(root.left,k-1)+getKLeafSize(root.right, k-1);
return val;
}
// 获取当前二叉树的高度
public int getHeight(Node root){
if(root==null){
return 0;
}
return 1+Math.max(getHeight(root.left),getHeight(root.right));
}
// 查找二叉树的某个节点
public Node find(Node root,char val){
if(root==null){
return null;
}
if(root.val==val){
return root;
}
Node leftNode=find(root.left,val);
if(leftNode.val==val){
return leftNode;
}
Node rightNode=find(root.right,val);
if(rightNode.val==val){
return rightNode;
}
return null;
}
}
递归的实现都是在栈上进行的,如果我们要用非递归的方式实现一棵二叉树,那么我们的核心思想就是创建一个栈,并在这个栈上模拟递归。
代码示例:
public void preOrderTraversal(Node root){
if(root==null){
return;
}
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
System.out.print(cur.val+" ");
cur=cur.left;
}
Node top=stack.pop();
cur=top.right;
}
}
代码示例:
public void inOrderTraversal(Node root){
if(root==null){
return;
}
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left
}
Node top=stack.pop();
System.out.print(top.val+" ");
cur=top.right;
}
}
代码示例:
public void posOrderTraversal(Node root){
if(root==null){
return;
}
Node prev=null;
Stack stack=new Stack<>();
Node cur=root;
while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
Node top=stack.peek();
cur=top.right;
if(curnull||cur.valprev.val){
System.out.print(top.val+" ");
prev=stack.pop();
cur=null;
}
}
}
=============================================================================
题目(OJ 链接):
给你二叉树的根节点
root
,返回它节点值的前序遍历。
代码一: 子问题的思路:将左子树、右子树和根都存放进去
public List preorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
list.add(root.val);
List leftTree=preorderTraversal(root.left);
list.addAll(leftTree);
List rightTree=preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
代码二: 遍历思路:将每个节点都遍历一遍
List list=new ArrayList<>();
public List preorderTraversal(TreeNode root) {
if(root==null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
题目(OJ 链接):
给定一个二叉树的根节点
root
,返回它的中序遍历。
代码一: 子问题思路
public List inorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List leftTree=inorderTraversal(root.left);
list.addAll(leftTree);
list.add(root.val);
List rightTree=inorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
代码二: 遍历思路
List list=new ArrayList<>();
public List inorderTraversal(TreeNode root) {
if(root==null){
return list;
}
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
题目(OJ 链接):
给定一个二叉树,返回它的后序遍历。
代码一: 子问题思
public List postorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List leftTree=postorderTraversal(root.left);
list.addAll(leftTree);
List rightTree=postorderTraversal(root.right);
list.addAll(rightTree);
list.add(root.val);
return list;
}
代码二: 遍历思路
List list=new ArrayList<>();
public List postorderTraversal(TreeNode root) {
if(root==null){
return list;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
return list;
}
题目(OJ 链接):
给你两棵二叉树的根节点
p
和q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
代码:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p!=null&&qnull||pnull&&q!=null){
return false;
}
if(pnull&&qnull){
return true;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
题目(OJ 链接):
给你两棵二叉树
root
和subRoot
。检验root
中是否包含和subRoot
具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
代码:
class Solution {
public boolean isSameTree(TreeNode root,TreeNode subRoot){
if(root!=null&&subRootnull||rootnull&&subRoot!=null){
return false;
}
if(rootnull&&subRootnull){
return true;
}
if(root.val!=subRoot.val){
return false;
}
return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null){
return false;
}
if(isSameTree(root,subRoot)){
return true;
}
if(isSubtree(root.left,subRoot)){
return true;
}
if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
}
题目(OJ 链接):
给定一个二叉树,找出其最大深度。
代码:
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
题目(OJ 链接):
给定一个二叉树,判断它是否是高度平衡的二叉树。
代码一: 时间复杂度为 O(N2)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
if(Math.abs(leftDepth-rightDepth)>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
}
代码二: 时间复杂度为 O(N)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1){
return 1+Math.max(leftDepth,rightDepth);
}else{
return -1;
}
}
public boolean isBalanced(TreeNode root) {
return maxDepth(root)>=0;
}
}
题目(OJ 链接):
给定一个二叉树,检查它是否是镜像对称的。
代码:
class Solution {
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
if(leftTreenull&&rightTreenull){
return true;
}
if(leftTree!=null&&rightTreenull||leftTreenull&&rightTree!=null){
return false;
}
if(leftTree.val!=rightTree.val){
return false;
}
return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
}
public boolean isSymmetric(TreeNode root) {
if(root==null){
return false;
}
return isSymmetricChild(root.left,root.right);
}
}
题目(OJ 链接):
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
代码:
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main{
public static int i=0;
public static TreeNode createBinaryTree(String str){
if(str.length()==0){
return null;
}
TreeNode root=null;
if(str.charAt(i)==‘#’){
i++;
}else{
root=new TreeNode(str.charAt(i));
i++;
root.left=createBinaryTree(str);
root.right=createBinaryTree(str);
}
return root;
}
public static void inOrderTraversal(TreeNode root){
if(root==null){
return;
自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。
深知大多数Java工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!
因此收集整理了一份《2024年Java开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。
既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上Java开发知识点,真正体系化!
由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新!
如果你觉得这些内容对你有帮助,可以扫码获取!!(备注Java获取)
提前多熟悉阿里往年的面试题肯定是对面试有很大的帮助的,但是作为技术性职业,手里有实打实的技术才是你面对面试官最有用的利器,这是从内在散发出来的自信。
备战阿里时我花的最多的时间就是在学习技术上,占了我所有学习计划中的百分之70,这是一些我学习期间觉得还是很不错的一些学习笔记
我为什么要写这篇文章呢,其实我觉得学习是不能停下脚步的,在网络上和大家一起分享,一起讨论,不单单可以遇到更多一样的人,还可以扩大自己的眼界,学习到更多的技术,我还会在csdn、博客、掘金等网站上分享技术,这也是一种学习的方法。
今天就分享到这里了,谢谢大家的关注,以后会分享更多的干货给大家!
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取!
}
public class Main{
public static int i=0;
public static TreeNode createBinaryTree(String str){
if(str.length()==0){
return null;
}
TreeNode root=null;
if(str.charAt(i)==‘#’){
i++;
}else{
root=new TreeNode(str.charAt(i));
i++;
root.left=createBinaryTree(str);
root.right=createBinaryTree(str);
}
return root;
}
public static void inOrderTraversal(TreeNode root){
if(root==null){
return;
自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。
深知大多数Java工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!
因此收集整理了一份《2024年Java开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。[外链图片转存中…(img-Tagg2LA9-1713549071340)]
[外链图片转存中…(img-8RPdBjtL-1713549071343)]
[外链图片转存中…(img-0cwFlrsL-1713549071345)]
既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上Java开发知识点,真正体系化!
由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新!
如果你觉得这些内容对你有帮助,可以扫码获取!!(备注Java获取)
提前多熟悉阿里往年的面试题肯定是对面试有很大的帮助的,但是作为技术性职业,手里有实打实的技术才是你面对面试官最有用的利器,这是从内在散发出来的自信。
备战阿里时我花的最多的时间就是在学习技术上,占了我所有学习计划中的百分之70,这是一些我学习期间觉得还是很不错的一些学习笔记
我为什么要写这篇文章呢,其实我觉得学习是不能停下脚步的,在网络上和大家一起分享,一起讨论,不单单可以遇到更多一样的人,还可以扩大自己的眼界,学习到更多的技术,我还会在csdn、博客、掘金等网站上分享技术,这也是一种学习的方法。
今天就分享到这里了,谢谢大家的关注,以后会分享更多的干货给大家!
[外链图片转存中…(img-T2WVAu91-1713549071346)]
[外链图片转存中…(img-KenudgBr-1713549071348)]
[外链图片转存中…(img-HLXNose9-1713549071350)]
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。