21-01 月份刷题记录

01-01

// 解法一: 跳两格
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
      // 如果当前值为1, i每次加2
      // 如果当前值为0, 如果下一个值为0, 则 n-- (特判: 当前值为最后一个数时)
      for(int i = 0; i < flowerbed.length; i += 2) {
          if(flowerbed[i] == 0) {
              if(i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
                  n --;
              } else {
                  // 提前进入下一个1
                  i ++;
              }
          }
        }
        return n <= 0;
    }
}

// 解法二: 暴力遍历
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for(int i=0; i<flowerbed.length; i++) {
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
                n--;
                if(n <= 0) return true;
                flowerbed[i] = 1;
            }
        }

        return n <= 0;
    }
}

知识背景:

​ 二叉搜索树: 左节点的所有值一定小于右节点所有值, 高度相差不超过1

​ 中序遍历: 左 -> 中 -> 右

​ 前序遍历: 中 -> 左 -> 右

​ 后序遍历: 左 -> 右 -> 中

解题思路:

利用递归整理二叉树, 每次以中心为根, 左半部分为左子树, 右半部分为右子树. 先分别递归建立左子树和右子树, 然后令根节点的指针分别指向两棵子树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 主要思路: 
        // 1. 确定根节点为数组中间值
        // 2. 递归构造左右子树
        // 3. 维护根节点和左右子树之间的关系

        return build(0, nums.length - 1, nums);
    }
    public TreeNode build(int l, int r, int[] nums) {
        if(l > r) return null;
        int mid;
        mid = (l + r) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(l, mid - 1, nums);
        root.right = build(mid + 1, r, nums);

        return root;
    }
}

利用递归方法比较简单, 具体代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // 递归做法
        frontPrint(root, list);
        return list;
        // 非递归做法
    }

    public void frontPrint(TreeNode root, List<Integer> list) {
       if(root == null) {
           return;
       }
        list.add(root.val);
        frontPrint(root.left, list);
        frontPrint(root.right, list);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        mediumPrint(root, list);
        return list;
    }

    public void mediumPrint(TreeNode root,  List<Integer> list) {
       if(root == null) {
           return ;
       }
       mediumPrint(root.left, list);
       list.add(root.val);
       mediumPrint(root.right, list);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        mediumPrint(root, list);
        return list;
    }

    public void mediumPrint(TreeNode root,  List<Integer> list) {
       if(root == null) {
           return ;
       }
       mediumPrint(root.left, list);
       mediumPrint(root.right, list);
       list.add(root.val);
    }
}

后面会发表如何利用非递归方法实现上述三种遍历