二叉树的简单练习

目录

一、二叉树常见的 *** 作

1、统计二叉树的节点个数

2、统计二叉树中叶子节点的个数

3、求出第K层的节点个数（k<=树的高度）

4、求二叉树的高度

5、判断二叉树是否包含val值

二、二叉树leetcode基础练习题

1、Num144

 2、Num100

3、Num572

4、Num110

5、Num101

三、相关代码

---

一、二叉树常见的 *** 作 1、统计二叉树的节点个数

/**
     * 传入二叉树的根节点，就可以求出节点个数
     * @param root
     * @return
     */
    public int getNode(TreeNode root){
        if (root==null){
            return 0;
        }
        //此时二叉树不为空,此时知道一个根节点root，那么根节点的左右子树的节点数就交给子函数处理
        //总结点数=1（根节点root）+左子树的所有节点+右子树的所有节点
        return 1+getNode(root.left)+getNode(root.right);
    }

2、统计二叉树中叶子节点的个数

 /**
     * 传入二叉树的根节点，就可以求职叶子节点数
     * @param root
     * @return
     */
    public int getLeafNode(TreeNode root){
        if (root==null){
            return 0;
        }
        if ((root.left==null)&&(root.right==null)){
            //此时说明只有一个根节点
            return 1;
        }
        //此时root不为空且有子树
        //总叶子节点数=左子树的叶子节点数+右子树的叶子节点数
        return getLeafNode(root.left)+getLeafNode(root.right);
    }

3、求出第K层的节点个数（k<=树的高度）

/**
     * 传入二叉树的根节点，就可以直到第k层的节点个数
     * @param root
     * @return
     */
    public int getKNode(TreeNode root,int k){
        if (root==null||k<0){
            return 0;
        }
        if (k==1){
            //k=1时就是根节点
            return 1;
        }
        //以root为根的第k层节点个数=以root.left为根的第k-1层节点个数+以root.right为根的第k-1层节点个数
        return getKNode(root.left,k-1)+getKNode(root.right,k-1);
    }

4、求二叉树的高度

/**
     * 传入二叉树的根节点，就可以知道树的高度
     * @param root
     * @return
     */
    public int rootHeight(TreeNode root){
        if (root==null) {
            return 0;
        }
        //二叉树的高度=1+（左子树高度和右子树高度的最大值）
        return 1+Math.max(rootHeight(root.left),rootHeight(root.right));
    }

5、判断二叉树是否包含val值

/**
     * 判断二叉树是否包含指定值val
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode root,E val){
        if (root==null){
            return false;
        }
        //此时根节点就是要找的节点
        if (root.val.equals(val)){
            return true;
        }
        //如果不是根节点，就继续在左子树和右子树查找
        return contains(root.left,val)||contains(root.right,val);
    }

二、二叉树leetcode基础练习题 1、Num144

package binary_tree.LeetCode;


import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的前序遍历，注意返回值
 */
public class Num144 {
    List data=new ArrayList<>();
    public List preorderTraversal(TreeNode root) {
         if (root==null){
             return data;
         }
         //前序遍历，根左右
        data.add(root.val);
         //递归左子树
        preorderTraversal(root.left);
        //递归右子树
        preorderTraversal(root.right);

        return data;
    }

}

 2、Num100

package binary_tree.LeetCode;

/**
 * 盘算两个二叉树是否完全相同
 * 先判断p和q的根节点是否相同
 * 然后左子树和右子树的判断交给子函数
 */
public class Num100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //两个二叉树都为空
        if (p==null&&q==null){
            return true;
        }
        //两个二叉树有一个为空
        if (p==null||q==null){
            return false;
        }
        //此时两个二叉树都不为空
        //先比较根节点的值是否相同
        //如果根节点相同，接下来左子树和右子树的判断交给子函数处理
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

3、Num572

package binary_tree.LeetCode;

/**
 * 判断是否包含子树
 * root和subRoot就是相同的树||root.left中包含subRoot||root.right中包含sunRoot
 */
public class Num572 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root==null&&subRoot==null){
            return false;
        }
        if (root==null||subRoot==null){
            return false;
        }
        //root和subRoot就是相同的树||root.left中包含subRoot||root.right中包含sunRoot
        return isSameTree(root, subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //两个二叉树都为空
        if (p==null&&q==null){
            return true;
        }
        //两个二叉树有一个为空
        if (p==null||q==null){
            return false;
        }
        //此时两个二叉树都不为空
        //先比较根节点的值是否相同
        //如果根节点相同，接下来左子树和右子树的判断交给子函数处理
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

4、Num110

package binary_tree.LeetCode;
/**
 * 判断是否为平衡二叉树，在二叉树中每个节点的左右高度差<=1
 */
public class Num110 {

    public boolean isBalanced(TreeNode root) {
      if (root==null){
          return true;
      }
      //求左子树的高度
        int left=rootHeight(root.left);
      //求右子树的高度
        int right=rootHeight(root.right);
        int num=Math.abs(left-right);
        //判断是否为平衡二叉树，在二叉树中每个节点的左右高度差<=1
        return num<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    /**
     * 传入二叉树的根节点，就可以知道树的高度
     * @param root
     * @return
     */
    public int rootHeight(TreeNode root){
        if (root==null) {
            return 0;
        }
        //二叉树的高度=1+（左子树高度和右子树高度的最大值）
        return 1+Math.max(rootHeight(root.left),rootHeight(root.right));
    }

}

5、Num101

package binary_tree.LeetCode;

/**
 * 判断二叉树是否镜像对称
 * 根节点的左子树和右子树的值相等&&左子树的左树和右子树的右树镜像相等&&左子树的右树和右子树的左树镜像相等
 */
public class Num101 {

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isMirror(root.left,root.right);
    }
    /**
     * 传入两个二叉树的根节点，就可以判断两个二叉树是否镜像相等
     * r1.val==r2.val&&r1.left==r2.right&&r1.right==r2.left
     * @param r1
     * @param r2
     * @return
     */
    public boolean isMirror(TreeNode r1,TreeNode r2){
        if (r1==null&&r2==null){
            return true;
        }
        if (r1==null||r2==null){
            return false;
        }
        return r1.val== r2.val&&isMirror(r1.left,r2.right)&&isMirror(r1.right,r2.left);
    }

}

三、相关代码

任枭雄/rocket_class_ds - Gitee.comhttps://gitee.com/ren-xiaoxiong/rocket_class_ds/tree/master/src/binary_tree