## Monday, August 8, 2016

### 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没有这种规定。

(3) Full tree有哪些特点?

(4) 怎么证明？

[Solution]
[#1 Solution]

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

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是输出所有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();`
`      ``}`
`    ``}`
`  ``}`
`}`