代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

222.完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

提供参数：根结点root

主要操作：遍历所有节点，记录节点数。

代码（递归法）大致如下：

    public int countNodes(TreeNode root) {
        if(root==null)return 0;
        int res;
        int left=countNodes(root.left);
        int right=countNodes(root.right);
        res=left+right+1;
        return res;
    }

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

提供参数：根结点root

主要操作：

递归三要素

1.返回值类型和提供参数：

以int作为返回值类型，-1标记高度不平衡，不为-1则说明高度平衡，提供参数为根结点root

2.终止条件：

如果节点为空，返回0

3.单层逻辑：

获取左子树高度，如果为-1直接返回-1

获取右子树高度，如果为-1直接返回-1

计算左右子树高度绝对值，如果大于1，直接返回-1

如果不大于1，返回该结点高度（1+子树高度更大的高度）

通过递归函数的返回值来判断，如果为-1则返回false，如果不为-1则返回true

代码大致如下：

    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        int res=getheight(root);
        if(res==-1)return false;
        else return true;        
    }
    public int getheight(TreeNode root){
        if(root==null)return 0;

        int left=getheight(root.left);
        if(left==-1)return -1;
        int right=getheight(root.right);
        if(right==-1)return -1;

        int res=0;
        if(Math.abs(left-right)>1)return -1;
        else{
            res=1+Math.max(left,right);
            return res;
        }
    }