打印二叉树的边界节点

[编程题]打印二叉树的边界节点

热度指数：1029 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树的根节点 root，按照如下两种标准分别实现二叉树的边界节点的逆时针打印。

标准一：

1，根节点为边界节点。

2，叶节点为边界节点。

3，如果节点在其所在的层中是最左的或最右的，那么该节点也是边界节点。

标准二：

1，根节点为边界节点。

2，叶节点为边界节点。

3，树左边界延伸下去的路径为边界节点。

4，树右边界延伸下去的路径为边界节点。

ps:具体请对照样例

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出两行整数分别表示按两种标准的边界节点。

示例1

输入

输出

1 2 4 7 11 13 14 15 16 12 10 6 3
1 2 4 7 13 14 15 16 10 6 3

备注:

算法知识视频讲解

Java

HGWXX7

import java.util.*;
class Node
{
int val;
Node left;
Node right;

public Node(int val)
{
this.val = val;
}
}

public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int len = in.nextInt();
Node[] map = new Node[len + 1];
int root = in.nextInt();
map[root] = getNode(root);
for (int i = 2; i <= len; i++)
{
int parent = in.nextInt();
int l = in.nextInt();
int r = in.nextInt();
map[l] = getNode(l);
map[r] = getNode(r);
map[parent].left = map[l];
map[parent].right = map[r];
}

print1(map[root]);
print2(map[root]);
}

public static Node getNode(int i)
{
if (i < 1)
return null;

return new Node(i);
}

public static void print1(Node head)
{
if (head == null)
return;

int height = getHeight(head);
Node[][] map = new Node[height][2];
setMap(map, head, 0);
for (int i = 0; i < height; i ++)
{
System.out.print(map[i][0].val + " ");
}

printLeafNode(map, head, 0);

for (int i = height - 1; i >= 0; i--)
{
if (map[i][0] != map[i][1])
{
System.out.print(map[i][1].val + " ");
}
}

System.out.println();
}

public static void printLeafNode(Node[][] map, Node head, int k)
{
if (head == null)
return;

if (head != map[k][0]
&& head != map[k][1]
&& head.left == null
&& head.right == null)
{
System.out.print(head.val + " ");
}
else
{
printLeafNode(map, head.left, k + 1);
printLeafNode(map, head.right, k + 1);
}
}

public static void setMap(Node[][] map, Node head, int k)
{
if (head == null)
return;

map[k][0] = map[k][0] == null ? head : map[k][0];
map[k][1] = head;
setMap(map, head.left, k + 1);
setMap(map, head.right, k + 1);
}

public static int getHeight(Node head)
{
if (head == null)
return 0;

return 1 + Math.max(getHeight(head.left),
getHeight(head.right));
}

private static void print2(Node node)
{
if (node == null)
return;

System.out.print(node.val + " ");
if (node.left != null && node.right != null)
{
printLeft(node.left, true);
printRight(node.right, true);
}
else
{
print2(node.left == null ? node.right : node.left);
}

System.out.println();
}

private static void printRight(Node node, boolean print)
{
if (node == null)
return;

printRight(node.left, print && node.right == null);
printRight(node.right, print);
if (print || (node.left == null && node.right == null))
{
System.out.print(node.val + " ");
}
}

private static void printLeft(Node node, boolean print)
{
if (node == null)
return;

if (print || (node.left == null && node.right == null))
{
System.out.print(node.val + " ");
}

printLeft(node.left, print);
printLeft(node.right, print && node.left == null);
}
}