Tree

  • While adding nodes to Queue, what you add is the reference, removed is the reference, it will not remove the actual TreeNode.
  • you cannot add 'null' to a Queue.
  • Queue is an abstract class, cannot implement as Queue nodes = new Queue(). it must be like LinkedList(); or DelayQueue....

  • Stack is a subclass of Vector. Stack can insert null in it. However, queue is an abstract class, it can be implemented by using List like LinkedList. The only method in Queue that illustrate it is the end of the queue is POLL. However, poll will return null if queue is empty. If insert null in a queue, when poll() returns a null, you cannot tell whether it is an empty or the inserted value.

  • Path题可以把path的sum在变量里变化，这样，当path发生变化的时候，sum随之发生变化。如果使用外部变量，则外部变量不在recursion中，需要人工手动加减，非常不方便。

  • return值：如果是return一个path上的值，通常是||， Math.min， Math.max等等，如果是所有path相加，通常是+，-等等

  • ||: 两根遍历有符合值即可 Math.min, Math.max: 两根遍历找最大/最小

  • recursion的变化值可以是传递函数，亦可以是return value。判断是否为真的时候用传递函数变换，用int的时候使用返回值变换。

  • 使用外部变量一般是整个recursion是单向的变化，比如说只是增大或是只是减小，否则就要在recursion里变换很多次。

  • // 似乎用boolean的题可以用 return xxx && yyy来做， int的题可以用 return xxx + yyy来做

  • you must make sure the node is not null to reuse it!

          if (root.left != null) {
          invertBinaryTree(root.left);
      }
      if (root.right != null) {
          invertBinaryTree(root.right);
      }
  • reference的问题说几次也不嫌多。最初只定义了一个全局变量path来存储满足sum = target的路径，然后改变路径和相对应的sum的值得出路径，但是只得到了两个空arraylist，原因是当遍历完时，path指向的地址里面装的是空的arraylist。而加入list里的恰恰是path的地址，所以返回两个空的arraylist[[],[]].
    • 解决方法是定义一个局部变量，每次当满足条件的时候，将会变化的全局变量复制到新的局部变量中，每次全局变量修改的时候都对这个每次都新构建的局部变量没有影响
  • minimum depth 不再是左右两棵树的比较，而是到leaf的长度的比较，不是leaf的长度都不能count。因此要判断左右子树是否有一个为空。如果为空，则不能让它经历撞墙的过程，因为撞了墙就会有一个该子树的返回值影响结果。因此要用if语句来防止左右子树之一为空的那个空子树撞墙。
  • Traverse:
    • level order: BFS, Queue
    • 树的遍历要看哪里撞墙。因为撞墙值会对返回值造成影响。要看是遍历path到leaf还是是否到leaf并没有影响。
    • 如果仅遍历一次，则应用if语句判断，一般是到leaf终止。
  • Path:
    • recursion产生变化的量可以是传递函数也可以是返回值，作比较是否相等时放在传递函数中，可以实时监控函数的变化，看level多大时可以用返回值
    • ||: 两根遍历有符合值即可；Math.min, Math.max: 两根遍历找最大/最小
    • 第二次的update,我用了只扫描path的方法，因为数level这种还是直接用path的template省的用脑子想了。
    • 要排除左或右为空的情况，因为path只算到达leaf的长度
    • (112)本题的boolean和symmetric的boolean并不一样，symmetric的boolean是每一步都在找boolean，因此用返回参数很好。这道题是寻找有没有这样一个值，因此用外部参数比较好。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        return helper(root);
    }
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return 1 + helper(root.right);
        }
        if (root.right == null) {
            return 1 + helper(root.left);
        }
        return 1 + Math.max(helper(root.left), helper(root.right));
    }
}
  • 对root.left或root.right操作时，需要确定其不为空。
  • boolean的题return xxx&&yyy 或者xxx || yyy
  • int的题return XXX + yyy
  • list的题
  • 要把tree连起来肯定要有一个node.left = new node的过程，不能只定义new node