题目一

题目

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

题解

递归。

代码

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public int TreeDepth(TreeNode root) {
        if(root==null) {
            return 0;
        }
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }
}

题目二

题目

判断二叉树是不是平衡二叉树。注意，此处定义的平衡二叉树：递归地，左右两个子树相差<=1。而不需要二叉搜索树条件。

题解

后序遍历，返回值包含是否平衡和当前子树高度。每个节点只需遍历一遍。

代码

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

class ReturnType{
    boolean balanceTag;
    int deepth;
    ReturnType(boolean balanceTag,int deepth){
        this.balanceTag=balanceTag;
        this.deepth=deepth;
    }
}

public class Main {
    public static void main(String[] args) {
        //test case
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node4.left=node5;

        System.out.println(isBalanced(node1).balanceTag);
    }

    public static ReturnType isBalanced(TreeNode root){
        if(root==null) {
            return new ReturnType(true,0);
        }
        ReturnType r1=isBalanced(root.left);
        ReturnType r2=isBalanced(root.right);
        int dif=Math.abs(r1.deepth-r2.deepth);
        int deepth=Math.max(r1.deepth, r2.deepth)+1;
        if(r1.balanceTag&&r2.balanceTag&&dif<=1) {
            return new ReturnType(true,deepth);
        }
        return new ReturnType(false,deepth);
    }
}