/**
* This problem was asked by Yahoo.
Recall that a full binary tree is one in which each node is either a leaf node, or has two children.
Given a binary tree, convert it to a full one by removing nodes with only one child.
For example, given the following tree:
0
/ \
1 2
/ \
3 4
\ / \
5 6 7
You should convert it to:
0
/ \
5 4
/ \
6 7
* */
class Problem_793 {
/*
* solution: post-order:left->right->root, to check each node's children if null.
* we form the new tree bottom up, starting from the leaves towards the root.
* By the time we process the current node, both its left and right subtrees were already processed.
* */
fun covertTreeToFull(node: Node?): Node? {
if (node == null) {
return null
}
node.left = covertTreeToFull(node.left)
node.right = covertTreeToFull(node.right)
if (node.left == null && node.right == null) {
return node
}
if (node.left == null) {
return node.right
}
if (node.right == null) {
return node.left
}
return node
}
class Node(value: Int) {
var left: Node? = null
var right: Node? = null
}
}