Binary Tree

每個 node 只有兩個 child，通常會用一個結構表示之：

public class TreeNode {
    public int val;
    public TreeNode left, right;
}

一些簡單的操作：

計算所有節點數：

public int getTreeNodesNumRecursion(TreeNode root) {
    if (root == null) {
        return 0;
    }

    return getTreeNodesNumRecursion(root.left) + getTreeNodesNumRecursion(root.right);
}

public int getTreeNodesNum(TreeNode root) {
    //level order
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> Q = new LinkedList<TreeNode>();
    Q.offer(root);

    int count = 0;
    while (!Q.isEmpty()) {
        TreeNode node = Q.poll();
        if (node.left) {
            Q.offer(node.left);
        }
        if (node.right) {
            Q.offer(node.right);
        }
        count++;
    }
    return count;
}

求樹的高度：

public int getDepthRecursion(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = getDepthRecursion(root.left);
    int right = getDepthRecursion(root.right);
    return Math.max(left, right) + 1;
}

//non-recursive 我們必須要知道什麼時候「換下一層」，可以用一個 dummy node 或是用額外的 count

public int getDepth(TreeNode root) {
   if (root == null) {
      return 0;
   }   

   int depth = 0;
   int count = 1;
   Queue<TreeNode> Q = new LinkedList<TreeNode>();
   Q.offer(root);
   while (!Q.isEmpty()) {
      depth++;
      int child_count = 0;
      for (int i = 0; i < count; i++) {
         TreeNode node = Q.poll();
         if (node.left != null) {
            Q.offer(node.left);
            child_count++;
         }
         if (node.right != null) {
            Q.offer(node.right);
            child_count++;
         }
      }
      count = child_count;
   }   
   return depth;
}