面试题：遍历三颗相连的满二叉树
题目：三颗满二叉树，他们的根节点互为父节点，从任意节点遍历整颗二叉树
要求：不能使用外部变量、集合等
不能改变树结构
不能 给节点添加额外属性
ps： 屁事真多
思路：一颗没毛病，就前序遍历就OK， 三颗也一样，但是要考虑到遍历根节点时死循环问题，方式为：如果一个节点是根节点，则设置标识， 并且只记录第一次碰到的的根节点， 还有一点，递归时要传过去当前节点，防止重复遍历
- 打印
- 遍历头
- 遍历左孩子
- 遍历右孩子
static class Node<E> {E v;Node<E> left;Node<E> right;Node<E> head;public Node(E v) {this.v = v;}
}/*** @param node* @param sourceNode 遍历到node节点的节点* @param firstRootNode 第一次碰到的根节点*/
private static void threeTreeTraversal(Node<Integer> node, Node<Integer> sourceNode, Node<Integer> firstRootNode) {if (null == node) {return;}// 先打印本节点值System.out.print(node.v + " ");// 如果一个节点是根节点，则设置标识，方式root节点之间死循环, 并且只记录第一次的根节点if (isRoot(node) && null == firstRootNode) {firstRootNode = node;}if (node.head != sourceNode && node.head != firstRootNode) {// 遍历头节点threeTreeTraversal(node.head, node, firstRootNode);}if (node.left != sourceNode) {// 遍历左子树threeTreeTraversal(node.left, node, firstRootNode);}if (node.right != sourceNode) {// 遍历右子树threeTreeTraversal(node.right, node, firstRootNode);}
}public static boolean isRoot(Node<Integer> node) {Node<Integer> parent = node.head;if (parent.left == node || parent.right == node) {return false;}return true;
}