探索二叉树的奇幻世界：解密二叉树的结构与遍历

文章目录

目录

一、二叉树的基本操作

1.1 获取树中节点的个数  

1.2 获取叶子节点的个数

1.3 获取第K层节点的个数

1.4 获取二叉树的高度

二、二叉树相关习题

2.1 检查两颗树是否相同

2.2 另一颗树的子树

2.3 翻转二叉树

2.4 判断一颗二叉树是否是平衡二叉树 

---

 一、二叉树的基本操作

public class TreeNode {static class treeNode{public char val;public treeNode left;       //储存左孩子的引用public treeNode right;      //储存右孩子的引用public treeNode(char val) {this.val = val;}}public treeNode creattree(){treeNode A=new treeNode('A');treeNode B=new treeNode('B');treeNode C=new treeNode('C');treeNode D=new treeNode('D');treeNode E=new treeNode('E');treeNode F=new treeNode('F');A.left=B;A.right=C;B.left=D;C.left=E;C.right=F;return A;}
}

函数creattree()用于创建一个简单的二叉树。函数中创建了六个treeNode对象，分别为A、B、C、D、E和F。然后，将每个节点的左子节点和右子节点分别设置为B和C、D和E、E和F，如下所示：

1.1 获取树中节点的个数  

//获取树中节点的个数public int size2(treeNode root) {if(root==null){return 0;}return size2(root.right)+size2(root.left)+1;}

    本章习题中很多都是采用递归的方法，求树中节点的个数一样，通过遍历二叉树的每个节点，计算叶子节点的数量。在递归过程中，函数会递归调 size2(root.left)和 size2(root.right)，计算左子树和右子树的叶子节点数量。最终，函数返回叶子节点的数量，表示二叉树中叶子节点的数量。

1.2 获取叶子节点的个数

 public int getLeftCount2(treeNode root){if(root==null){return 0;}if(root.left!=null&&root.right!=null){return 1;}return getLeftCount2(root.left)+getLeftCount2(root.right);
}

 1.3 获取第K层节点的个数

//获取第K层节点的个数public int getLevelNodeCount(treeNode root,int key){if(root==null){return 0;}if(key==1){return 1;}return getLevelNodeCount(root.right,key-1)+getLevelNodeCount(root.left,key-1);}

1.4 获取二叉树的高度

//获取二叉树的高度public int getHeight(treeNode root){if(root!=null){return 0;}int rightH=getHeight(root.right);int leftH=getHeight(root.left);return Math.max(rightH,leftH)+1;}

二、二叉树相关习题

2.1 检查两颗树是否相同

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p!=null&&q==null||p==null&&q!=null){return false;}if(p==null&&q==null){return true;}if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

2.2 另一颗树的子树

借用2.1的方法判断两个树是否相同，

1、递归的过程树的根节点一直在变化，首先判断树是否为空

2、判断当前根节点是否与子树相同

3、分别用根节点的左子树和右子树分别判断是否与子树相同（注意：不用isSameTree的原因是isSameTree只会判断一次，就结束了）

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root==null){return false;}if(isSameTree(root,subRoot)) return true;if(isSubtree(root.right,subRoot))return true;if(isSubtree(root.left,subRoot))return true;return false;}public boolean isSameTree(TreeNode p, TreeNode q) {if(p!=null&&q==null||p==null&&q!=null){return false;}if(p==null&&q==null){return true;}if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

2.3 翻转二叉树

思路：

        遍历二叉树的每个节点 ，使其左右节点进行互换，然后递归左右节点，返回根节点 

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}TreeNode p=root.left;root.left=root.right;root.right=p;invertTree(root.left);invertTree(root.right);return root;}
}

2.4 判断一颗二叉树是否是平衡二叉树

 

思路：

        1、借用1.4获取二叉树高度的函数

        2、遍历改树的每一个节点，求每个节点的的左子树和右子树高度的差是不是大于2，是则返回false

        3、若小于二&&左子树是不是平衡二叉树&&右子树是不是平衡二叉树

class Solution {public boolean isBalanced(TreeNode root) {if(root==null){return true;}int leftHight=getHeight(root.left);int rightHight=getHeight(root.right);return Math.abs(leftHight-rightHight)<2&&isBalanced(root.left)&&isBalanced(root.right);}public int getHeight(TreeNode root){if(root==null){return 0;}int leftHight=getHeight(root.left);int rightHight=getHeight(root.right);return Math.max(leftHight,rightHight)+1;}
}