数据结构在二叉树Oj中利用子问题思路来解决问题
本章是关于二叉树数据结构：来源于Leetcode oj题。感谢大家的观看！！！希望大家的技术会越来越好！！我的博客主页
获取二叉树的节点数
首先从左树开始递到最下一层，当最后一层H没有节点时，归回+1以此类推，最终返回的节点就是我们树的节点树。
public int getNodeCount(TreeNode root){
if(root==null)return 0;
return getNodeCount(root.left)+getNodeCount(root.right)+1;
}获取二叉树的终端节点个数
首先清楚二叉树的终端结点是什么？ 终端结点说明它的度为0（没有子树），所以左树和右树的值为null，而我们就只需要判断一下，如果左树和右树值为null，则就是一个叶子结点+1.
public int getLeafCount(TreeNode root){
if(root==null)return 0;
if(root.left==null&&root.right==null){
return 1;
}
return getLeafCount(root.left)+getLeafCount(root.right);
}获取k层节点的个数
第一层为我们的根节点，它的个数一定是1，而根的左树和右树则为2，以此类推
我们的第一个条件是k为1时一定会有一个节点数 这里当我们递出去时，我们就会减少一层当k等于1时，这里我们就在k层找到一个节点然后回归到父节点然后继续子树找下一个节点，知道将k层的节点数遍历完。
public int getLevelCount(TreeNode root,int k){
if(root==null)return 0;
if(k==1)return 1;
return getLevelCount(root.left,k-1)+getLevelCount(root.right,k-1);
}获取二叉树的高度
这里直接求左子树的最大高度和右子树的最大高度然后进行比较，然后返回最大的高度值就可以
public int getBinaryTreeHeight(TreeNode root){
if(root==null)return 0;
int maxtLeftHeight=getBinaryTreeHeight(root.left);
int maxRightHeight=getBinaryTreeHeight(root.right);
return maxLeftHeight>maxRightHeight?maxLeftHeight+1:maxRightHeight+1;
}检测为value的元素是否存在
首先root根和递归的条件不能为空 然后判断root的值是否为value值并返回这个值 用一个ret来接收其返回值，然后判断ret不为空，则回来的值将root的value值带回 （ret如果为空，说明root根或者递归的条件就是空的，没有要找的元素）
public TreeNode find(TreeNode root,String val){
if(root==null)return null;
if(root.val.equals(val)) return root;
TreeNode ret1 = find(root.left,val);
if(ret1!=null)return ret1;
TreeNode ret2 = find(root.right,val);
if(ret2!=null)return ret2;
return null;
}判断两颗树是否相同
判断两颗树是否相同 首先根节点到叶子结点两者的结构相同 然后是根节点到叶子结点的值要相同 如果说一棵树为空但是另一个树不为空，说明两棵树的结构一定是不同的 如果两颗树都为空，加上上述说明两棵树的结构一致 接下来判断节点的值 两颗树的节点值如果不一样，则也不是相同的 最后判断两颗树左树和右树是否一致
public boolean isSameTree(TreeNode tree1,TreeNode tree2){
//两棵树如果同时走一个有节点一个没有节点一定不相同
if(tree1==null&&tree2!=null||tree1!=null&&tree2==null)return false;
//两棵树都为null说明都没有可以走的节点
if(tree1==null&&tree2==null)return true;
//判断结构
//判断节点值是否相同不同为false
if(!tree1.val.equals(tree2.val)return false;
return isSameTree(tree1.left,tree2.left)&&isSameTree(tree1.right,tree2.right);
}判断是否是另一棵的子树
判断是否是tree中的一颗子树，subtree一定是t在ree中头节点左子树中或者是右子树中，如果不在这里直接返回false 这里由tree的左子树和右子树递归找到subtree的根节点，找到后将tree中的subtree子树与subtree同时遍历来确认是否为一个相同的树。
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//是相同的树节点返回true
if(isSameTree(root,subRoot))return true;
//递归如果出现root为null时，因为没有语句拦截，root会继续往下走导致空指针异常
//subRoot为null直接返回false，主树不在进行下面的递归
if(root==null||subRoot==null)return false;
if(isSubtree(root.left,subRoot))return true;
if(isSubtree(root.right,subRoot))return true;
return false;
}反转二叉树
将二叉树的每个节点的左子树和右子树互换
public TreeNode invertTree(TreeNode root) {
if(root==null)return null;
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}判断一颗二叉树是否是平衡二叉树
时间复杂度O(n*n)
该题判断二叉树是否是平衡二叉树的条件是：左子树与右子树的绝对值一定小于或者等于1，如果高度大于1则非平衡二叉树。 如果根节点只有一个节点或者他的左右子树差的绝对值为0，则为平衡二叉树
只判断了根的节点的话它的左右子树的差确实为1，但是左子树中b的左子树和右子树的差值为2，这也不是一个平衡的二叉树。
public boolean isBalanced(TreeNode root) {
if(root==null)return true;//root为null直接返回为空
int leftHeight = maxDepth(root.left);//求左树的高度
int rightHeight = maxDepth(root.right);//求右树的高度
return Math.abs(leftHeight-rightHeight)<=1//判断
&&isBalanced(root.left)&&isBalanced(root.right);
}
public int maxDepth(TreeNode root){
//求二叉树的最大深度
if(root==null)return 0;
int leftHeight=maxDepth(root.left);
int rightHeight=maxDepth(root.right);
return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}复杂度O(N)
这里如果我们在找左右子树高度的差值时如果发现了它差值大于1的情况，我们直接返回-1，当最后回归到根节点左右子树时，差值也大于1
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)return true;
int ret =maxDepth(root);
//接收ret为-1则左右子树差值一定大于1
if(ret==-1){
return false;
}
return true;
}
public int maxDepth(TreeNode root){
//求二叉树的最大深度
if(root==null)return 0;
int leftHeight=maxDepth(root.left);
int rightHeight=maxDepth(root.right);
//走到这里最靠下的边上的左右子树求得高度
if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
//说明左右子树的绝对值为<=1并且大于等于0
//返回左右子树中最大的一个高度+1
return Math.max(leftHeight,rightHeight)+1;
}else{
return -1;
}
}
}二叉树的遍历
首先创建一个类来实现构造二叉树的前提 因为题目条件给定的是输入一串字符串然后先序遍历这个字符串来建立起二叉树，然后通过中序遍历在进行打印
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 void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str=in.nextLine();
TreeNode root=createTree(str);
inOrder(root);
}
}
public static TreeNode createTree(String str) {
TreeNode root=null;
//遍历字符串str来获取字符来给到root，因为不确定root是不是空节点。
if (str.charAt(i) != '#') {
root =new TreeNode(str.charAt(i));
i++;
//通过i++来递归左右树
root.left=createTree(str);
root.right=createTree(str);
} else {
//跳过#
i++;
}
return root;
}
//中序遍历
public static void inOrder(TreeNode root) {
if (root == null)return ;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}判断是否是对称的二叉树
二叉树反转过来的镜像就是对称的二叉树 这里直接从根节点的左树和右树下手 满足条件1:二叉树的结构相同 满足条件2:二叉树的对称值相同 左子树中的左树对应右子树的右树 右子树的左树对应左子树的右树
public boolean isSymmetric(TreeNode root) {
if(root==null)return true;
//判断左右节点是否对称
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode t1,TreeNode t2){
//这里t1和t2的结构不相同
if(t1==null&&t2!=null||t1!=null&&t2==null)return false;
//两者都为空，说明结构相同走向空节点
if(t1==null&&t2==null)return true;
//到这里结构相同检查对称值
if(t1.val!=t2.val)return false;
//满足左右子树的对称条件
return isSymmetricChild(t1.left,t2.right)
&&isSymmetricChild(t1.right,t2.left);
}二叉树的层序遍历
二叉树层序遍历是地1层开始从左到右，从上到下开始遍历。 如果用二维数组来进行层序遍历怎么做呢？ 这里需要用到队列，因为第一层的根节点永远是1，我们将它放入到队列中来遍历这个队列 如果a释放完且a树的值给到了一维数组后，会得到b和c两个子树并放到队列中，这时候需要一个计数器来计算当前的层数，当层数为0时，我们将一维数组所有的值放到二维数组中就好了
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> line=new ArrayList<List<Integer>>();
if(root==null)return line;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
List<Integer> col=new ArrayList<Integer>();
while(size!=0){
TreeNode cur = queue.poll();
col.add(cur.val);
size--;
if(cur.left!=null) queue.offer(cur.left);
if(cur.right!=null) queue.offer(cur.right);
}
line.add(col);
}
return line;
}从前序与中序遍历序列构造二叉树
这里给了一个前序数组，给了一个中序数组，而前序数组第一个值就是我们的根节点，我们在中序数组中找到根节点来确定左右树，左边为左子树，右边为右子树。当获取到前序数组的第一个元素后我们进行查找并返回由中序数组中的下标，然后递归左树的end节点-1（左树的返回在根节点-1的位置），如果begin>end，说明end已经减到-1，没有任何元素，这时遍历右树，右树的节点在根节点右侧，让其右侧数组起始位置+1直到>最后的位置.
public int preIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild
(preorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int[] preorder ,int[] inorder, int begin ,int end){
if(begin>end)return null;
//来记录前序遍历的下标
TreeNode root=new TreeNode(preorder[preIndex]);
//这个下标的值在中序中里找到
int inIndex = findIndex(inorder,begin,end,preorder[preIndex]);
if(inIndex==-1)return null;
//中序找完后前序加加，来找下一个
preIndex++;
root.left=buildTreeChild(preorder,inorder,begin,inIndex-1);
root.right=buildTreeChild(preorder,inorder,inIndex+1,end);
return root;
}
private int findIndex(int[] inorder,int begin,int end,int key){
for(int i=begin;i<=end;i++){
if(inorder[i]==key){
return i;
}
}
return -1;
}二叉树的层序遍历||
通过尾叉法来进行插入，第一行就是最后一行，创建一个队列来存储每一行，通过计数器的方式将每一行的元素给到列中，当计数器为0，跳出size循环后将其add到line中。
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list=new ArrayList<List<Integer>>();
if(root==null)return list;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list2=new LinkedList<>();
int size=queue.size();
while(size!=0){
TreeNode cur = queue.poll();
list2.add(cur.val);
size--;
if(cur.left!=null)queue.offer(cur.left);
if(cur.right!=null)queue.offer(cur.right);
}
//尾叉法
list.add(0,list2);
}
return list;
}腾讯云开发者
