代码随想录二刷第二十一天 | 222.完全二叉树的节点个数、110.平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和、513.找树左下角的值

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

思路

可以用简单的前序递归遍历实现，也可以用完全二叉树的性质实现。

下面给出完全二叉树性质代码

代码

时间复杂度：O(logN × logN) 空间复杂度：O(logN)

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int leftDepth = 1, rightDepth = 1;
        TreeNode left = root.left, right = root.right;
        while(left != null){
            left = left.left;
            leftDepth++;
        }
        while(right != null){
            right = right.right;
            rightDepth++;
        }
        if(leftDepth == rightDepth){
            return (int) Math.pow(2, leftDepth) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110.平衡二叉树

思路

平衡二叉树是左右子树高度不超过1

注意区分深度和高度，深度是从上往下，高度是从下往上

1. 先求左右子树的高度，如果左右子树不为平衡二叉树，就返回-1
2. 再对比左右子树高度差是否小于1，否则返回-1
3. 父节点的高度 = 左右子树高度的最大值 + 1

代码

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    
    private int getHeight(TreeNode node){
        if(node == null) return 0;
        int leftHeight = getHeight(node.left);
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(node.right);
        if(rightHeight == -1) return -1;
        if(Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

257. 二叉树的所有路径

思路

简单的回溯题

代码

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {
    List res = new ArrayList();
    public List binaryTreePaths(TreeNode root) {
        func(root, \"\");
        return res;
    }
    private void func(TreeNode node, String str){
        if(node == null) return;
        if(node.left == null && node.right == null){
            res.add(str + node.val);
            return;
        }
        str += node.val + \"->\";
        func(node.left, str);
        func(node.right, str);
    }
}

404. 左叶子之和

思路

如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子

代码

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return sum;
        }
        if(root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum;
    }
}

513.找树左下角的值

思路

层序遍历

代码

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Deque q = new LinkedList();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            res = q.peek().val;
            while(size > 0){
                TreeNode node = q.poll();
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                size--;
            }
        }
        return res;
    }
}

112. 路径总和

思路

回溯计算，注意考虑只有根节点的情况，并且只有到叶子节点的时候才判断和是否满足条件。

代码

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
         if(root == null) return false;
         return deal(root, targetSum, 0);
    }
    private boolean deal(TreeNode node, int targetSum, int sum){
         if(node == null) return false;
         sum += node.val;
         if(sum == targetSum && node.left == null && node.right == null) return true;
         return deal(node.left, targetSum, sum) || deal(node.right, targetSum, sum);
    }
}