打印二叉树的边界节点

//
// Created by yuanhao on 2019-9-2.
//

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

// 计算深度和访问顺序
void edge0(int root, const int *lch, const int *rch, vector<int> *visit_orders, int *depth, int dep) {
    depth[root] = dep;
    visit_orders[dep].push_back(root);
    if (lch[root] != 0) {
        edge0(lch[root], lch, rch, visit_orders, depth, dep + 1);
    }
    if (rch[root] != 0) {
        edge0(rch[root], lch, rch, visit_orders, depth, dep + 1);
    }
}

// 所有叶节点
void edge1(int root, int *lch, int *rch, bool *output, bool *is_right) {
    if (lch[root] != 0) {
        edge1(lch[root], lch, rch, output, is_right);
    }
    if (rch[root] != 0) {
        edge1(rch[root], lch, rch, output, is_right);
    }
    if (lch[root] == 0 && rch[root] == 0 && !output[root] && !is_right[root]) {
        cout << root << " ";
        output[root] = true;
    }
}

void edge2(int root, int *lch, int *rch, bool left, bool right, bool *output) {
    // 左路径
    if (left && !output[root]) {
        cout << root << " ";
        output[root] = true;
    }
    if (lch[root] != 0) {
        edge2(lch[root], lch, rch, left, right && rch[root] == 0, output);
    }
    if (rch[root] != 0) {
        edge2(rch[root], lch, rch, left && lch[root] == 0, right, output);
    }
    // 叶节点
    if (lch[root] == 0 && rch[root] == 0 && !output[root]) {
        cout << root << " ";
        output[root] = true;
    }
    //右路径
    if (!output[root] && right) {
        cout << root << " ";
        output[root] = true;
    }
}

//题目描述
//给定一颗二叉树的根节点 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
//输入
//复制
//16 1
//1 2 3
//2 0 4
//4 7 8
//7 0 0
//8 0 11
//11 13 14
//13 0 0
//14 0 0
//3 5 6
//5 9 10
//10 0 0
//9 12 0
//12 15 16
//15 0 0
//16 0 0
//输出
//复制
//1 2 4 7 11 13 14 15 16 12 10 6 3
//1 2 4 7 13 14 15 16 10 6 3
int main() {
    int n = 0;
    int root = 0;
    cin >> n >> root;
    int lch[n + 1];
    int rch[n + 1];
    for (int i = 0; i < n; ++i) {
        int f, l, r;
        cin >> f >> l >> r;
        lch[f] = l;
        rch[f] = r;
    }
    // 前面是输入

    // 第一种情况，
    // 这种情况其实题目是有问题的，顺序的问题，并不是你所以为的逆时针顺序，而是下面的顺序，
    // 先输出每层最左节点，再输出既不是每层最左节点也不是每层最右节点的叶节点，最后从下往上输出每层最右节点
    // 我也是看了出错的用例才从里面看出来的，此题略坑

    bool output[n + 1]; // 是否已经输出了这个节点，一个节点可能既是每层最左节点，又是每层最右节点，又是子节点
    memset(output, 0, sizeof(bool) * (n + 1));
    int depth[n + 1]; // 节点深度
    vector<int> visit_orders[n + 1]; // 访问顺序
    memset(depth, 0, sizeof(int) * (n + 1));

    // 先序遍历，获取节点深度和访问顺序，每层最左节点是本层先被访问的，最右节点是本层最后被访问的
    edge0(root, lch, rch, visit_orders, depth, 0);

    bool is_right[n + 1]; // 是否本层最右节点
    memset(is_right, 0, sizeof(bool) * (n + 1));
    // 输出每层最左边节点
    for (int dep = 0; dep <= n; ++dep) {
        vector<int> level = visit_orders[dep];
        if (!level.empty()) {
            cout << level[0] << " ";
            output[level[0]] = true;
            is_right[level[level.size() - 1]] = true;
        }
    }
    // 第二次遍历，输出既不是每层最左节点，也不是每层最右节点的叶节点
    edge1(root, lch, rch, output, is_right);
    // 输出每层最右节点
    for (int dep = n; dep >= 0; --dep) {
        vector<int> level = visit_orders[dep];
        if (!level.empty() && !output[level[level.size() - 1]]) {
            cout << level[level.size() - 1] << " ";
            output[level[level.size() - 1]] = true;
        }
    }
    cout << endl;

    // 第二种情况
    memset(output, 0, sizeof(bool) * (n + 1));
    edge2(root, lch, rch, true, true, output);
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
/*
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};

void createTree(TreeNode* root,int cnt)
{
    if(!cnt) return;
    int p,l,r;
    cin>>p>>l>>r;
    if(l)
    {
        TreeNode* node = new TreeNode(l);
        root->left = node;
        createTree(root->left,cnt-1);
    }
    if(r)
    {
        TreeNode* node = new TreeNode(r);
        root->right = node;
        createTree(root->right,cnt-1);
    }
}
*/
/// 标准一的打印规则
int getHeight(int root,int* lc,int* rc)
{
    if(!root)  return 0;
    else return 1 + max(getHeight(lc[root],lc,rc),getHeight(rc[root],lc,rc));
}
void setEdgeMap(int root,int* lc,int* rc,int i,vector<vector<int>>& v)
{
    if(!root) return;
    v[i][0] = v[i][0] == -1 ? root : v[i][0];
    v[i][1] = root;
    setEdgeMap(lc[root],lc,rc,i+1,v);
    setEdgeMap(rc[root],lc,rc,i+1,v);
}
void printLeafNotInMap(int root,int* lc,int* rc,int i,vector<vector<int>>& v,vector<int>& ans)
{
    if(!root) return;
    if(lc[root]==0 && rc[root]==0 && root != v[i][0] && root != v[i][1])
        ans.push_back(root);
    printLeafNotInMap(lc[root],lc,rc,i+1,v,ans);
    printLeafNotInMap(rc[root],lc,rc,i+1,v,ans);
}

void printEdge1(int root, int* lc,int* rc,vector<int>& ans)
{
    if(!root) return;
    int h = getHeight(root,lc,rc);
    vector<vector<int>>v(h,vector<int>(2,-1));
    setEdgeMap(root,lc,rc,0,v);
    for(int i=0;i<h;++i)
        ans.push_back(v[i][0]);
    printLeafNotInMap(root,lc,rc,0,v,ans);
    for(int i=h-1;i>=0;--i)
    {
        if(v[i][0]!=v[i][1])
            ans.push_back(v[i][1]);
    }
}
// 标准二打印

void printLeftEdge(int root,int* lc,int* rc,bool print,vector<int>& ans)
{
    if(!root) return;
    if(print || (lc[root]==0 && rc[root]==0 ))
        ans.push_back(root);
    printLeftEdge(lc[root],lc,rc,print,ans);
    bool p = print && lc[root] == 0 ? true:false;
    printLeftEdge(rc[root],lc,rc,p,ans);
}
void printRightEdge(int root,int* lc,int* rc,bool print,vector<int>& ans)
{
    if(!root) return ;
    int p = print && rc[root]==0 ? true:false;
    printRightEdge(lc[root],lc,rc,p,ans);
    printRightEdge(rc[root],lc,rc,print,ans);
    if(print|| (!lc[root] && !rc[root]))
        ans.push_back(root);
}
void printEdge2(int root,int* lc,int* rc,vector<int>& ans)
{
    if(!root) return;
    ans.push_back(root);
    if(lc[root]!=0 && rc[root]!= 0)
    {
        printLeftEdge(lc[root],lc,rc,true,ans);
        printRightEdge(rc[root],lc,rc,true,ans);
    }
    else
    {
        int r =  lc[root]!= 0 ? lc[root] : rc[root];
        printEdge2(r,lc,rc,ans);
    }
}



int main()
{
    int n,root;
    cin>>n>>root;
    //TreeNode* root = new TreeNode(root_val);
    //createTree(root,N);int n, root, t;
    //cin >> n >> root;
    int* lc = new int[n + 1];
    int* rc = new int[n + 1];
    int p;
    for (int i = 0; i < n; i++) 
    {
        cin >> p;
        cin >> lc[p] >> rc[p];
    }
    vector<int>ans;
    printEdge1(root,lc,rc,ans);
    for(int i:ans) cout<<i<<" ";
    cout<<endl;
    ans.clear();
    printEdge2(root,lc,rc,ans);
    for(int i:ans) cout<<i<<" ";
    cout<<endl;
    return 0;
}

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);
    }
}

恶心到我了，菜鸟不知道怎么将输入转化为二叉树，求大神解答

#include<iostream>
using namespace std;
class Node{
public:
    int val;
    Node* left;
    Node* right;
    Node(int data){this->val=data;}
    int getData(){return val;}
    void setValue(int num){this->val=num;}
    void setLeft(Node* left){this->left=left;}
    void setRight(Node* right){this->right=right;}
};

int getHeight(Node* h,int l){
    if(h==nullptr)
        return l;
    return max(getHeight(h->left,l+1),getHeight(h->right,l+1));
}

void setEdgeMap(Node* h,int l,vector<vector<Node*>>& edgeMap)
{
    if(h==nullptr)
        return;
    edgeMap[l][0]=edgeMap[l][0]==nullptr?h:edgeMap[l][0];
    edgeMap[l][l]=h;
    setEdgeMap(h->left,l+1,edgeMap);
    setEdgeMap(h->right,l+1,edgeMap);
}

void printLeafNotInMap(Node* h,int l,vector<vector<Node*>>& m){
    if(h==nullptr)
        return;
    if(h->left==nullptr&&h->right==nullptr&&h!=m[1][0]&&h!=m[1][1]){
        cout<<h->val<<" ";
    }
    printLeafNotInMap(h->left,l+1,m);
    printLeafNotInMap(h->right,l+1,m);
}

void printEdge1(Node* head)
{
    if(head==nullptr)
        return;
    int height=getHeight(head,0);
    vector<vector<Node*>>edgeMap(height,vector<Node*>(2));
    setEdgeMap(head,0,edgeMap);
    int size=edgeMap.size();
    //打印左边界
    for(int i=0;i!=size;++i)
    {
        cout<<edgeMap[i][0]->val<<" ";
    }
    //打印既不是左边界，也不是右边界
    printLeafNotInMap(head,0,edgeMap);
    //打印右边界，但不是左边界的节点
    for(int i=size-1;i!=-1;--i)
    {
        if(edgeMap[i][0]!=edgeMap[i][1]){
            cout<<edgeMap[i][1]->val<<" ";
        }
    }
    cout<<endl;
}

void printLeftEdge(Node* h,bool print){
    if(h==nullptr)return;
    if(print||(h->left==nullptr&&h->right==nullptr))
        cout<<h->val<<" ";
    printLeftEdge(h->left,print);
    printLeftEdge(h->right,print&&h->left==nullptr?true:false);
}

void printRightEdge(Node* h,bool print){
    if(h==nullptr)return;
    printRightEdge(h->left,print&&h->right==nullptr?true:false);
    printRightEdge(h->right,print);
    if(print||(h->left==nullptr&&h->right==nullptr))
        cout<<h->val<<" ";
}

void printEdge2(Node* head){
    if(head==nullptr)return;
    cout<<head->val<<" ";
    if(head->left!=nullptr&&head->right!=nullptr){
        printLeftEdge(head->left,true);
        printRightEdge(head->right,true);
    }else{
        printEdge2(head->left!=nullptr?head->left:head->right);
    }
    cout<<endl;
}

int main()
{
    int nodesnum;
    cin>>nodesnum;
    Node* nodes[nodesnum];
    int val;
    nodes[val]->setValue(val);
    Node* root=nodes[val];
    for(int i=0;i<=nodesnum;++i)
    {
        do{
            int fa,lch,rch;
            cin>>fa;
            bool exit=false;
            for(int i=0;i<nodesnum;++i)
            {
                if(fa==nodes[i]->getData())
                    exit=true;
            }
            if(!exit)
            {
                nodes[fa]->setValue(fa);
            }
            exit=false;
            cin>>lch;
            for(int i=0;i<nodesnum;++i)
            {
                if(lch==nodes[i]->getData())
                    exit=true;
            }
            if(!exit)
            {
                nodes[lch]->setValue(lch);
            }
            nodes[fa]->setLeft(nodes[lch]);
            exit=false;
            cin>>rch;
            for(int i=0;i<nodesnum;++i)
            {
                if(rch==nodes[i]->getData())
                    exit=true;
            }
            if(!exit)
            {
                nodes[rch]->setValue(rch);
            }
            nodes[fa]->setLeft(nodes[rch]);
        }while(getchar()!='\n');
    }
    printEdge1(root);
    printEdge2(root);
    return 0;
}