Google – Generate All Full Trees with N Leaves / h Height

Google – Generate All Full Trees with N Leaves / h Height
n leaves的full tree有多少种可能性？ 输出所有full tree？
h heights的full tree有多少种可能性？ 输出所有full tree？
[Analysis]
(1) a什么是full tree?
Full tree是一种binary tree, 其中每个node，要么没有children，要么就有两个children。
(2) Full tree和Complete tree的区别?
Complete tree除了最后一层，其他层都必须是满的，而full tree没有这种规定。
另外Complete tree可以出现只有一个child的情况，而full tree不允许。
(3) Full tree有哪些特点?
如果full tree有n个leaves，那么total number of nodes = 2 * n – 1.
(4) 怎么证明？
简单的方法：
可以想象成一个1 v 1的game, 比到最后只会有一个大赢家，那么就会有 n – 1个internal node, 因为除了最后的赢家，其他每个玩家只会输一次且仅有一次。
严格的方法：
数学归纳法，假设n – 1个leaves成立，有2 * (n – 1) – 1 = 2 * n – 3个nodes。如果要新增加一个leaf，因为full tree的特性，必须加入两个children到其中一个leaf上，这样leaves减一加二就等于n，那么总共的node数量就+2， 2 * n – 3 + 2 = 2 * n – 1.

[Solution]
[#1 Solution]
方法类似于leetcode的unique binary tree，对于root来说，如果left subtree包含k个leaves, 那么right subtree就必须包含n – k个leaves. 无需考虑奇偶的情况，因为奇数leaves也一样能组成一棵full tree.

T(n) = T(k) + T(n – k), k ∈ [1, n – 1]

[#2 Solution]
固定height的做法有点难，因为对于root来说，只需要left subtree或者right subtree其中之一的height为h – 1就可以了。比如left subtree的height为h – 1，那么对于right subtree，它的高度可以是[1, h – 1]之间的任何一个值。另外对于root，left和right subtree属于对称的情况。

T(n) = 2 * T(n – 1) * (T(1) + T(2) + … + T(n – 1)) – T(n – 1) * T(n – 1)
left/right subtree 高度都为h – 1的情况算了两次，所以要减掉一次。

[Note]
第二题的code有一点要特别注意，因为left subtree和right subtree是属于对称情况，一开始直接两种对称情况一起加入到leftSub和rightSub的lists里面，再通过两层for循环建当前的tree。
但是这样会出现bug，比如高度为1的left subtree会和高度也为1的right subtree组成新的tree。这样是不对的，高度为1的left subtree只能和高度为h – 1的right subtree组成新tree。
还有一点optimization是写这篇Post的时候才想到的，Solution2里面第57和第71两行可以放到for loop外面，可以省掉不少递归。（因为这两行递归h – 1，递归里还有n多递归呢）。

Code是输出所有full tree，计算数量可以通过上面递推式求得。

// n leaf nodes

class Solution {

  public List<TreeNode> allFullTrees(int n) {

    List<TreeNode> result = new ArrayList<>();

    if (n == 0) {

      return result;

    }

    if (n == 1) {

      result.add(new TreeNode(1));

      return result;

    }

 

    for (int i = 1; i < n; i++) {

      List<TreeNode> leftSub = allFullTrees(i);

      List<TreeNode> rightSub = allFullTrees(n - i);

 

      for (TreeNode l : leftSub) {

        for (TreeNode r : rightSub) {

          TreeNode root = new TreeNode(1);

          root.left = l;

          root.right = r;

          result.add(root);

        }

      }

    }

 

    return result;

  }

}

 

// h height

// T(n) = 2 * T(n - 1) * (T(1) + T(2) + ... + T(n - 1)) - T(n - 1) * T(n - 1)

class Solution2{

  public List<TreeNode> allFullTrees(int h) {

    List<TreeNode> result = new ArrayList<>();

    if (h == 0) {

      return result;

    }

 

    buildTree(h, result);

    return result;

  }

 

  private void buildTree(int h, List<TreeNode> result) {

    if (h == 0) {

      return;

    }

    if (h == 1) {

      result.add(new TreeNode(1));

      return;

    }

 

    List<TreeNode> leftSub = new ArrayList<>();

    List<TreeNode> rightSub = new ArrayList<>();

    for (int i = 1; i < h; i++) {

      buildTree(i, leftSub);

      buildTree(h - 1, rightSub);

      for (TreeNode l : leftSub) {

        for (TreeNode r : rightSub) {

          TreeNode root = new TreeNode(1);

          root.left = l;

          root.right = r;

          result.add(root);

        }

      }

      leftSub.clear();

      rightSub.clear();

 

      if (i != h - 1) {

        buildTree(i, rightSub);

        buildTree(h - 1, leftSub);

 

        for (TreeNode l : leftSub) {

          for (TreeNode r : rightSub) {

            TreeNode root = new TreeNode(1);

            root.left = l;

            root.right = r;

            result.add(root);

          }

        }

        leftSub.clear();

        rightSub.clear();

      }

    }

  }

}

Read full article from Google – Generate All Full Trees with N Leaves / h Height