小猿给定了一棵完全二叉树，树中结点都是正整数，请问该完全二叉树的边界结点从根结点开始以逆时针的顺序排序后形成的序列是什么？
边界结点定义为每层最左边的结点、叶子结点和每层最右边的结点。（同一个结点只能计入一次）
[编程题]完全二叉树的边界
中规中矩的求解方法，先层次重构完全二叉树。
（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));
//打印最左边的
for(int i = 0; i < lastLayer; i++){
System.out.print(nodes[(int)Math.pow(2,i) - 1]);
System.out.print(' ');
System.out.print(nodes[i - 1]);
System.out.print(' ');
System.out.print(nodes[i - 1]);
System.out.print(' ');
System.out.print(nodes[(int)Math.pow(2,i) - 1 - 1]);
System.out.print(' ');
}
}
}
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)
# 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)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
