LeetCode刷题Day14——二叉树（完全二叉树、平衡二叉树、二叉树路径、左叶子之和）

/**
 * <pre>
 * 1.二分查找+位运算
 * 2.递归：如果子树是完全二叉树则直接返回子树的节点数，如果不是完全二叉树则继续判断其左右子树
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 10:54
 */
public class 完全二叉树的节点个数222 {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode node = root;
        int h = 0;
        while (node.left != null) {
            h++;
            node = node.left;
        } // 求出最大高度
        int left = 1 << h, right = (1 << (h+1)) - 1; // 最下一层节点的标号
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (check(root, h, mid)) {
                // 该节点存在，则往右查找
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
    public boolean check(TreeNode root, int height, int index) {
        int bits = 1 << (height-1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            // &运算可以用来求一个数中的指定位，将要判断的那一位置为1，其他位为0，然后用这个数和指定数想与，结果如果为0就说明对应位置为0，结果如果不为0就说明对应位置为1
            // 此处我们要判断index的第二位到结束的每一位是0还是1来决定是往左走还是往右走，这里用bits来控制
            // 最开始bits=1<<(height-1)其实就是一个首位为1(因为是height-1所以这里的首位对应的是index的第二位)，其他都为0的数
            // 然后每次判断后就对bits右移1位，即然后1后移以判断index后面的位是否为1
            // 比如index=5，即101，首位不用看，第二位0就说明从根节点先像左走，第三位为1就说明第二步是往右走即可到达结点5
            if ((index & bits) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }
    public int countNodes2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftHeight = 0, rightHeight = 0;
        while (left != null) {
            left = left.left;
            leftHeight++;
        }
        while (right != null) {
            right = right.right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (1 << (leftHeight+1)) - 1;
        }
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }
}

/**
 * <pre>
 * 1.自顶向下递归，不断求左右节点的高度判断差值是否大于1(每个节点的高度会被重复计算)
 * 2.自底向上递归，采用后续遍历，从最下的节点开始，求其左右节点高度，判断是否平衡，如果不平衡则整棵树不平衡，如果平衡则继续往上判断
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 14:33
 */
public class 平衡二叉树110 {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) { // 判断当前节点左右子树是否平衡
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right); // 如果平衡则继续往下判断左右子节点
    }
    public int getHeight(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        return Math.max(getHeight(treeNode.left), getHeight(treeNode.right)) + 1;
    }
    public boolean isBalanced2(TreeNode root) {
        return getHeight2(root) >= 0;
    }
    public int getHeight2(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftHeight = getHeight2(treeNode.left);
        int rightHeight = getHeight2(treeNode.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // 相当于后续遍历，到最下面一个节点后判断其左右子树是否平衡，不平衡则返回-1，如果子节点的高度已经是-1了则肯定不平衡了直接返回-1
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

/**
 * <pre>
 * 1.深度优先搜索
 * 2.广度优先搜索
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 23:46
 */
public class 二叉树的所有路径227 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        traversal(res, new StringBuilder(), root);
        return res;
    }
    public void traversal(List<String> res, StringBuilder path, TreeNode root) {
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) {
            res.add(path.toString() + root.val); // 不能用path.append后再toString，会导致path值改变
            return;
        }
        int len = path.length();
        path.append(root.val).append("->");
        if (left != null) {
            traversal(res, path, left);
        }
        if (right != null) {
            traversal(res, path, right);
        }
        path.delete(len, path.length()); // 回溯
    }
    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> res = new ArrayList<>();
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<String> pathQueue = new LinkedList<>();
        nodeQueue.offer(root);
        pathQueue.offer(String.valueOf(root.val));
        while (!nodeQueue.isEmpty()) {
            TreeNode treeNode = nodeQueue.poll();
            String path = pathQueue.poll();
            if (treeNode.left == null && treeNode.right == null) {
                res.add(path);
            }
            if (treeNode.left != null) {
                nodeQueue.offer(treeNode.left);
                pathQueue.offer(path + "->" + treeNode.left.val);
            }
            if (treeNode.right != null) {
                nodeQueue.offer(treeNode.right);
                pathQueue.offer(path + "->" + treeNode.right.val);
            }
        }
        return res;
    }
}

/**
 * <pre>
 * 1.深搜
 * 2.广搜
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/15 23:46
 */
public class 左叶子之和404 {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + (root.left != null && root.left.left == null && root.left.right == null ? root.left.val : 0); // 等于左子树左叶子节点和+右子树左叶子节点和
    }
    public int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                if (poll.left.left == null && poll.left.right == null) {
                    sum += poll.left.val;
                } else {
                    queue.offer(poll.left);
                }
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return sum;
    }
}