每日刷题记录 (七)

第一题: 剑指 Offer II 043. 往完全二叉树添加节点

LeetCode: 剑指 Offer II 043. 往完全二叉树添加节点
描述:
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的根节点。
  

解题思路:

1. 这里的初始化, 就让一个root等于当前root就可以了.
2. 这里的插入, 插入之后是一颗完全二叉树, 返回的是父亲节点的值.
   这里有两种情况
   1. 当前节点个数为偶数, 插入到最后一个节点父亲节点的右节点处,
   2. 当前节点个数为奇数, 插入到父亲节点的下一节点的左节点处(层序遍历).
      

代码实现:

class CBTInserter {
    
    private TreeNode root;
    public CBTInserter(TreeNode root) {
    
        this.root = root;
    }
    
    public int insert(int v) {
    
        TreeNode newNode = new TreeNode(v);
        // 当还没有节点的时候, 直接让插入的节点为头节点
        if (root == null) {
    
            root = newNode;
            return root.val;
        }
        // 这里使用层序遍历的方法, 将所有节点记录下来
        List<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            while (size != 0){
    
                TreeNode top = queue.poll();
                list.add(top);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
        }
        // 这里是解决个数为奇数和偶数的.
        if(list.size() % 2 == 0) {
    
            TreeNode parent = list.get((list.size()-1)/2);
            parent.right = newNode;
            return parent.val;
        }else{
    
            TreeNode parent = list.get(list.size()/2);
            parent.left = newNode;
            return parent.val;
        }
    }
    
    public TreeNode get_root() {
    
        return root;
    }
}

第二题: 剑指 Offer II 044. 二叉树每层的最大值

LeetCode: 剑指 Offer II 044. 二叉树每层的最大值
描述:
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

解题思路:

1. 这里使用层序遍历的方法.
2. 每次记录每层的最大值 max
3. 将max记录下来, 然后返回

代码实现:

class Solution {
    
    public List<Integer> largestValues(TreeNode root) {
    
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            while (size != 0){
    
                TreeNode top = queue.poll();
                // 得到最大值max
                max = Math.max(top.val,max);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
            // 记录max
            ret.add(max);
        }
        return ret;
    }
}

第三题: 剑指 Offer II 045. 二叉树最底层最左边的值

LeetCode: 剑指 Offer II 045. 二叉树最底层最左边的值
描述:
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

解题思路:

1. 这里是使用层序遍历的思路, 区别就是每次遍历都是从右往左.
2. 每次让ret=当前遍历的值
3. 遍历结束, ret的值就是最左的值

代码实现:

class Solution {
    
    public int findBottomLeftValue(TreeNode root) {
    
        int ret = 0; 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
    
        	// 这里直接进行遍历, 不需要每层每层的遍历
            TreeNode top = queue.poll();
            if(top.right != null) queue.offer(top.right);
            if(top.left != null) queue.offer(top.left);
            // 让ret的值指向top.val的值
            ret = top.val;
        }
        // 遍历结束, ret的值就是最左值
        return ret;
    }
}

第四题: 剑指 Offer II 046. 二叉树的右侧视图

LeetCode: 剑指 Offer II 046. 二叉树的右侧视图
描述:
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路:

1. 这里也是使用层序遍历的方法
2. 每层遍历的时候, 只要当前size=1 就添加到list中.
3. 遍历结束, 每层的最右侧节点的值就添加完了.

代码实现:

class Solution {
    
    public List<Integer> rightSideView(TreeNode root) {
    
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            while (size != 0){
    
                TreeNode top = queue.poll();
                // 当size=1 就是该层最后的一个值.
                if(size == 1) ret.add(top.val);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
        }
        return ret;
    }
}

第五题: 剑指 Offer II 047. 二叉树剪枝

LeetCode: 剑指 Offer II 047. 二叉树剪枝
描述:
给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

解题思路:

遍历节点,
如果 root为空, 返回 null
如果 该节点为叶子节点, 且当前为0, 就让该父节点指向null
这里使用后序遍历的方法.

代码实现:

class Solution {
    
    public TreeNode pruneTree(TreeNode root) {
    
        if(root == null) return null;
        // 左 -> 右 -> 根
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        // 这里的 root如果是叶子节点, 且当前为0, 就让他为null
        if (root.val == 0 && root.left == null && root.right == null) {
    
            return null;
        }
        return root;
    }
}

第六题: 剑指 Offer II 049. 从根节点到叶节点的路径数字之和

LeetCode: 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
描述:
给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。

解题思路:

• 这里的计算公式就是 : total = total*10 + root.val;
• 当走到叶子节点的时候, 就把这个值记录下来.

代码实现:

class Solution {
    
    int sum = 0;
    public int sumNumbers(TreeNode root) {
    
        getTotal(root,0);
        return sum;
    }
    public void getTotal(TreeNode root, int total) {
    
        if(root == null) return;
        // 这里计算total
        total = total*10 + root.val;
        // 当为叶子节点, 这一条就算完了.需要加起来.
        if(root.left == null && root.right == null) {
    
            sum += total;
        }
        getTotal(root.left,total);
        getTotal(root.right,total);
    }
}