Diameter of a binary tree

• 这种求最佳但是may or may not pass the root node，其实隐含的意思就是结果是Max or Min(each node)，即搜索所有的children获得结果。

• 而这样的搜索结果不一定直接可以去得到，却可以通过在遍历子树的过程中，间接进行ans的判断进而获取全局的答案

  class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return 0;
        depth(root);
        return ans - 1;
    }
  
    private int depth(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        int l = depth(root.left);
        int r = depth(root.right);
        ans = Math.max(ans, l + r + 1);
        return 1 + Math.max(l, r);
    }
  }
  

Count Complete TreeNodes

• 遇到Complete Binary Tree，考虑从Height入手
• Height可以通过不断的向左获取
• 因为要考虑最后的一层结束在哪里，而最后一层一定是左对齐，所以考虑从右子树的节点入手，如果右子树高度为
  1. h-1，那么说明最后一层的最后一个点在右子树上，即左子树是满的，所以问题就只跟以root.right为根的complete bt有关，构成了一个sub problem
  2. h-2，那么说明最后一层的最后一个点在左子树上，即右子树是满的(高度为h-2)，所以问题就只跟以root.left为根的complete bt有关，同样构成了一个sub problem

public int countNodes(TreeNode root) {
        int count = 0;
        if (root == null) return count;
        int h = getHeight(root);
        int rightH = getHeight(root.right);
        if (rightH == h - 1) {
            //the last node is on the right subtree
            int left = (1 << (h-1)) - 1;
            return 1 + left + countNodes(root.right);
        } else {
            //h-1, in this case the last node is on the left subtree,
            //so the right subtree is a complete tree with a height of h-2
            int right = (1 << rightH) - 1;
            return 1 + right + countNodes(root.left);
        }
    }

    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + getHeight(root.left);
    }