首页 > 试题广场 >

完全二叉树的边界

[编程题]完全二叉树的边界
  • 热度指数：159 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小猿给定了一棵完全二叉树，树中结点都是正整数，请问该完全二叉树的边界结点从根结点开始以逆时针的顺序排序后形成的序列是什么？
边界结点定义为每层最左边的结点、叶子结点和每层最右边的结点。（同一个结点只能计入一次）

输入描述:
第一行输入一个正整数 N，表示为完全二叉树的结点个数（1 ≤ N ≤ 106）。
第二行输入 N 个正整数，表示为该完全二叉树的层序遍历序列。


输出描述:
输出完全二叉树的边界结点从根结点开始以逆时针的顺序排序后形成的序列，以空格分隔。
示例1

输入

5
1 2 3 4 5

输出

1 2 4 5 3

说明

二叉树如下：
            1
          /    \
        2        3
      /    \     
    4       5 
算法知识视频讲解
添加回答
pein531头像 pein531
中规中矩的求解方法，先层次重构完全二叉树。
（1）从上到下让节点指针不断向左指得到左边界；
（2）利用二叉树的后序遍历，可以得到从左往右顺序的叶子节点；
（3）从上到下让节点指针不断向右指得到右边界；
由于获得右边界时需要的是从下往上的节点顺序，因此在此过程中用栈来存储节点值，避免之后的逆序操作，打印右边界的时候弹栈就行了。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) { this.val = val; }
}

public class Main {
    public static ArrayList<Integer> boundary = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] params = br.readLine().split(" ");
        int[] elements = new int[n];
        for(int i = 0; i < n; i++)
            elements[i] = Integer.parseInt(params[i]);
        // 重建完全二叉树
        TreeNode root = new TreeNode(elements[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ptr = 1;
        while(ptr < n){
            if(!queue.isEmpty()){
                TreeNode node = queue.poll();
                node.left = new TreeNode(elements[ptr]);
                queue.offer(node.left);
                ptr ++;
                if(ptr < n){
                    node.right = new TreeNode(elements[ptr]);
                    queue.offer(node.right);
                    ptr ++;
                }
            }
        }
        // 获得左边界
        TreeNode node = root;
        boundary.add(node.val);
        while(node.left != null){
            node = node.left;
            boundary.add(node.val);
        }
        boundary.remove(boundary.size() - 1);
        // 后序遍历获得叶子节点
        postOrder(root);
        boundary.remove(boundary.size() - 1);
        // 获得右边界
        node = root;      // 根节点已经算在左边界内，右边界不考虑
        Stack<Integer> rightBoundary = new Stack<>();
        while(node.right != null){
            node = node.right;
            rightBoundary.push(node.val);
        }
        for(int k = 0; k < boundary.size(); k++)
            System.out.print(boundary.get(k) + " ");
        // 右边界反着打印
        while(!rightBoundary.isEmpty())
            System.out.print(rightBoundary.pop() + " ");
    }
    
    private static void postOrder(TreeNode node) {
        if(node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        // 没有左孩子也没有右孩子，为叶子节点
        if(node.left == null && node.right == null) boundary.add(node.val);
    }
}

编辑于 2021-08-17 16:39:28 回复(0)
叹灵头像 叹灵
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int nodeNums = scanner.nextInt();
        int[] nodes = new int[nodeNums];
        int index = 0;
        while(scanner.hasNext()){
            nodes[index++] = scanner.nextInt();
            if(index == nodeNums){
                break;
            }
        }
        //计算这棵树的深度
        int lastLayer = (int)Math.floor(Math.log(nodeNums) / Math.log(2));

        //这棵树如果不满的话。可能倒数第二层也存在叶子节点，但绝对不会出现在倒数第三层及之前，因为这是完全二叉树的性质决定的
        int upLastLayerNode = nodeNums / 2;//根据树的最后一个节点的坐标找到它的父亲，也就是倒数第二层叶子节点的开始坐标

        //打印最左边的
        for(int i = 0; i < lastLayer; i++){
            System.out.print(nodes[(int)Math.pow(2,i) - 1]);
            System.out.print(' ');
        }
        //打印最后一层叶子节点
        for(int i = (int) Math.pow(2, lastLayer); i <= nodeNums; i++){
            System.out.print(nodes[i - 1]);
            System.out.print(' ');
        }
        //打印倒数第二层叶子节点
        for(int i = upLastLayerNode + 1; i < (int) Math.pow(2, lastLayer) - 1; i++){
            System.out.print(nodes[i - 1]);
            System.out.print(' ');
        }
        //打印最右边的
        for(int i = lastLayer; i > 1; i--){
            System.out.print(nodes[(int)Math.pow(2,i) - 1 - 1]);
            System.out.print(' ');
        }

    }
}
发表于 2022-08-05 16:23:09 回复(0)
牛客129782836号头像 牛客129782836号
# lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# n = len(lst);
 
# node = n
# left = 2n+1
# right = 2n+2
 
n =int(input())
st =input().split(" ")
lst =[int(x) forx inst]
 
leftLst =[]
botLst =[]
rightLst =[]
 
i =0
while(i < n):
    leftLst.append(lst[i])
    i =2*i+1
 
# find last row
m =0
k =1
while(m < n):
    k *=2
    m +=k
# last row start at m-1
botLst.extend(lst[k-1:])
# find second last row
kk =int(k/2)-1
while(kk < k-1):
    if(kk*2+1< n):
        pass
    else:
        botLst.append(lst[kk])
    kk+=1
j =2
while(j < n):
    rightLst.append(lst[j])
    j =2*j +2
 
rightLst.reverse()
rightLst.pop(0)
botLst.pop(0)
leftLst.extend(botLst)
leftLst.extend(rightLst)
 
strr =" ".join([str(x) forx inleftLst])
print(strr)
发表于 2021-07-31 14:10:02 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 2021 数据库工程师 测试开发工程师 猿辅导 大数据开发工程师 Java工程师
上传者：小小
难度：
3条回答 1083浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号