力扣刷题---二叉树--1

求二叉树结点个数

1、子问题思想,结点个数=左结点+右结点+根节点

//子问题思路,左右结点+1
        int getSize1(TreeNode root){
            if(root==null){
                return 0;
            }
            return getSize1(root.left)+getSize1(root.right)+1;
        }

解题过程:
力扣刷题---二叉树--1_第1张图片

2、遍历二叉树求结点个数

 //求结点个数,遍历思路
        int count=0;
       int getSize2(TreeNode root){
            if(root==null){
                return 0;
            }
            count++;
            getSize2(root.left);
            getSize2(root.right);
            return count;
        }

求叶子节点个数

1、子问题思路,叶子结点=左叶子结点+右叶子结点

     //子问题思路-求叶子结点个数
     int getLeafSize2(TreeNode root){
           if(root==null){
               return 0;
           }
           if(root.left==null && root.right==null){
               return 1;
           }
           return getLeafSize2(root.left)+getLeafSize2(root.right);
        }

2、遍历思路

// 遍历思路-求叶子结点个数
       static int leafSize = 0;//放外面,若放函数里面,每次递归都会被置0
       int getLeafSize1(TreeNode root){
           if(root==null){
               return 0;
           }
           if(root.left==null && root.right==null){
               leafSize++;
           }
           getLeafSize1(root.left);
           getLeafSize1(root.right);
           return leafSize;
        }

求第 k 层结点个数

解题思路:
力扣刷题---二叉树--1_第2张图片

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

二叉树的高度

解题思路:
力扣刷题---二叉树--1_第3张图片

 int getHeight(TreeNode root){
           if(root==null){
               return 0;
           }
           int lightLeft=getHeight(root.left);
           int lightRight=getHeight(root.right);
           return lightLeft>lightRight?lightLeft+1:lightRight+1;
        }

两棵树是否相同的树

解题思路:
力扣刷题---二叉树--1_第4张图片

//判断两棵树是否相同的树
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p==null&&q!=null){
                return false;
            }
            if(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);
        }

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

解题思路:
力扣刷题---二叉树--1_第5张图片

 public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p==null&&q!=null){
                return false;
            }
            if(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);
        }
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if(root==null||subRoot==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;
        }

小结

以上就是今天的内容了,有什么问题都可以在评论区留言✌✌✌
力扣刷题---二叉树--1_第6张图片

你可能感兴趣的