1. Balanced binary tree (*)

The definition of balanced binary tree: the absolute value of the difference between the height of the left and right subtrees is not more than 1, and the left and right subtrees are balanced binary trees

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return (Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lDepth = getHeight(root.left);
        int rDepth = getHeight(root.right);
        return Math.max(lDepth, rDepth) + 1; }}Copy the code
  1. Minimum depth of binary tree (*)

Create a new node and add depth to it. Perform breadth traversal, and when a leaf node is encountered, return the depth of that node. Because it is breadth traversal, the minimum depth must be returned at this point.

class Solution {
    class BtNode {
        TreeNode t;
        int depth;

        public BtNode(TreeNode root, int depth) {
            t = root;
            this.depth = depth; }}public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        BtNode bt = new BtNode(root, 1);
        Queue<BtNode> queue = new LinkedList<BtNode>();
        queue.add(bt);
        int depth = 0;
        while(! queue.isEmpty()) { depth = queue.peek().depth; BtNode tt = queue.poll();if (tt.t.left == null && tt.t.right == null) {
                return tt.depth;
            }
            if(tt.t.left ! =null) {
                queue.add(new BtNode(tt.t.left, depth + 1));
            }
            if(tt.t.right ! =null) {
                queue.add(new BtNode(tt.t.right, depth + 1)); }}return 0; }}Copy the code

Other ideas:

Copy the code
  1. Sum of paths (*)

If there is a path from the current node root to the leaf node, the sum of the paths is sum. Given that the sum of the values from the root node to the current node is val, we can turn the big question into a smaller one: is there a path from the children of the current node to the leaf whose sum is sum-val? If the current node is a leaf node, then we can directly determine whether sum is equal to val

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        returnhasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }}Copy the code