打印二叉树边界节点

· 310 words · 1 minute read
2017年7月
算法

题目：

给定一颗二叉树的头结点head,按照如下标实现二叉树边节点的逆时针打印

标准一：

1、头节点为边界节点
2、叶结点为边界节点
3、如果节点在其所在的层中是最左边或最右边，那么也是边界节点。

例如：如图所示的数

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

打印结果为：1,2,4,7,11,13,14,15,16,12,10,6,3

方法

个人认为主要的难点就在于怎么存储最左节点和最右节点。因此也就对此部分给出相应代码。

            最左节点        最右节点                                   
第一层         1           1
第二层         2           3
...

关键代码：

//生成一个二维数组存储最左节点和最右节点
Node[][] edgeMap = new Node[][2];


//先序遍历，最后最右节点会覆盖之前存储的最右节点
public void setEdgeMap(Node h, int l, Node[][] edgeMap){
    if(h == null){
        return;
    }
    edgeMap[l][0] = edgeMap[l][0] == null ? h : edgeMap[1][0];
    edgeMap[l][1] = h;
    setEdgeMap(h.left, l + 1, edgeMap);
    setEdgeMap(h.right, l + 1, edgeMap);
}
Share