## Monday, August 8, 2016

family tree就是左右指针分别指向自己的父亲和母亲。最小一代就是root，leaves是最老的一代。

1. 给一个Family tree, 给每个节点标出对应binary heap的id
2. 任意给一个节点（没有root的情况下），输出这个点所在的层数
3. 任意给一个节点（没有root的情况下），输出这点和root的关系，比如是root的父亲的母亲就输出"FM"
[Solution]

left child = 2 * id + 1
right child = 2 * id + 2
parent = (id – 1) / 2

`class` `Solution {`
`  `
`  ``public` `void` `setID(TreeNode root) {`
`    ``dfs(root, ``0``);`
`  ``}`
`  `
`  ``private` `void` `dfs(TreeNode curr, ``int` `val) {`
`    ``if` `(curr == ``null``) {`
`      ``return``;`
`    ``}`
`    ``curr.val = val;`
`    ``dfs(curr.left, val * ``2` `+ ``1``);`
`    ``dfs(curr.right, val * ``2` `+ ``2``);`
`  ``}`
`  `
`  ``public` `int` `getLevel(TreeNode node) {`
`    ``int` `level = ``0``;`
`    ``while` `((``1` `<< level) < node.val) {`
`      ``level++;`
`    ``}`
`    ``return` `level;`
`  ``}`
`  `
`  ``public` `String getRelations(TreeNode node) {`
`    ``StringBuilder sb = ``new` `StringBuilder();`
`    ``getParent((node.val - ``1``) / ``2``, node.val, sb);`
`    ``return` `sb.reverse().toString();`
`  ``}`
`  `
`  ``private` `void` `getParent(``int` `parentId, ``int` `id, StringBuilder sb) {`
`    ``if` `(id == ``0``) {`
`      ``return``;`
`    ``}`
`    ``if` `(parentId * ``2` `+ ``1` `== id) {`
`      ``sb.append(``"F"``);`
`    ``}`
`    ``else` `{`
`      ``sb.append(``"M"``);`
`    ``}`
`    `
`    ``getParent((parentId - ``1``) / ``2``, parentId, sb);`
`  ``}`
`}`