二叉树的性质

1、若规定根节点层数为1，一棵非空二叉树的第i层上最多有2的（i-1）次方个节点
2、高度为K的二叉树的最大节点数为2的K次方-1
3、一棵二叉树的叶子节点的个数为N1，非叶子节点的个数为N2，则N1=N2+1
4、具有n个节点的完全二叉树，其高度为log2（n+1）取整

求节点的个数

定义一个全局变量，通过前序遍历，中序遍历，后序遍历求节点的个数

    static int size = 0;
    public void getSize1(Node root){
        if(root == null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

左树的节点+右树的节点+本身（即为1）

    public int getSize2(Node root){
        if(root == null){
            return 0;
        }
        int leftSize = getSize2(root.left);
        int rightSize = getSize2(root.right);
        return leftSize + rightSize + 1;
    }

求叶子节点的个数

遍历思路，依旧是前序遍历的思路，定义一个静态变量count，遇到左右都为空的节点，count++

    static int count = 0;
    public void getLeafSize1(Node root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            count++;
            return;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

在这里插入图片描述

子问题思路
左树的叶子节点+右树的叶子节点

    public int getLeafSize2(Node root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

在这里插入图片描述

求第K层节点的个数

在这里插入图片描述

    public int getKLevelSize(Node root , int k){
        if(root == null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k-1) ;
    }

获取二叉树的高度

当前root 的高度等于左树的高度和右树高度的最大值 +1；

    public int Hight(Node root){
        if(root == null){
            return 0;
        }
        int leftHight = Hight(root.left);
        int rightHight = Hight(root.right);
        return (leftHight > rightHight ? leftHight : rightHight) + 1;
    }

在这里插入图片描述

查找节点

按照前序遍历的方式寻找，一旦找到，立即返回，不要继续在其他位置查找

子问题思路
1.判断节点是否是要寻找的节点
2.再找左子树和右子树
3.如果左子树返回一个非空的节点，那么就不用判断右子树了

    public Node find(Node root ,String val){
        if(root == null){
            return null;
        }
        if(root.getVal() == val){
            return root;
        }
        Node leftNode = find(root.left,val);
        if(leftNode != null){
            return leftNode;
        }
        return find(root.right , val);
    }

检查两棵树是否相同

判断节点是否相同，如果都为空，相同，返回true；一个为空，一个不为空，返回false；都不为空，但是值不同，返回false；
判断左子树和左子树是否相同，右子树和右子树是否相同

    public boolean isSame(Node rootA , Node rootB){
        if(rootA == null && rootB == null){
            return true;
        }
        if(rootA == null || rootB == null){
            return false;
        }
        if(rootA.getVal() != rootB.getVal()){
            return false;
        }
        return isSame(rootA.left,rootB.left) && isSame(rootA.right,rootB.right);
    }

判断一颗树是否是另一棵树的子树

判断两棵树是否是相同的，相同的返回true
如果root为空了，proot一定不是root的子树
在判断proot是不是root的左子树，proot是不是root的右子树

    public boolean isChild(Node root,Node proot){
        if(isSame(root,proot)){
            return true;
        }
        if(root == null){
        return false;
        }
        return isChild(root.left,proot) || isChild(root.right,proot);
    }