首页 > 试题广场 >

实现二叉树的后续遍历

[编程题]实现二叉树的后续遍历
  • 热度指数：77 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
代码实现二叉树的后续遍历。要求：1、不可以用递归；2、不可以用栈；3、自定义树节点的结构；4、给出测试用例；5、语言不限；
注意：你的方法的输入为根节点
参考方法：定义树结构体如下：
struct TreeNode {
    int value;
    TreeNode* parent;
    TreeNode* leftChild;
    TreeNode* rightChild;
}

输入描述:
第一行一个正整数n(1<=n<=100)，表示二叉树有n个结点。
接下来n行，第i行两个整数li,ri (0<=li,ri<=n) ，分别表示第i个结点的左儿子和右儿子，为0代表空。
保证根为1，保证输入为合法二叉树。


输出描述:
输出一行。输出n个数，代表后序遍历的结点的顺序，相邻两个数之间用一个空格相隔。
示例1

输入

5
3 2
0 5
0 4
0 0
0 0

输出

4 3 5 2 1
算法知识视频讲解
添加回答
{球球offer}头像 {球球offer} 
//我的TreeNode中保存了父节点、左子节点、右子节点的输入序号，默认为0为空节点
//构造一个n+1大小的TreeNode数组，下标0为空节点，其它下标对应节点的输入序号即value
//用一个下标指示根节点，按后续遍历顺序找到最先遍历的节点，并将指示下标赋值为该节点
//找到当前树中最先遍历的节点，其左右子节点都为空，输出该节点的下标即value，并将该节点从树中删除
//删除节点通过将其父节点的指向赋值为0，当父节点有左子节点时都会先删除左子节点

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
	//int value = 0;//输入的序号
	int parent = 0;
	int left = 0;
	int right = 0;
};
int main() {
	int n; 
	cin >> n;
	
	vector<TreeNode>arr(n+1);
	for (int i = 1; i <= n; i++)
		cin >> arr[i].left >> arr[i].right;



	for (int i = 1; i <= n; i++) {//节点的输入序号即节点的值
		int lef = arr[i].left;
		int rig = arr[i].right;
		arr[lef].parent = i;
		arr[rig].parent = i;
	}

	//后续遍历
	int index = 1;
	int count = 0;
	while (count < n) {
		int lef = arr[index].left;
		if (lef) {
			index = lef;
			continue;
		}
		int rig = arr[index].right;
		if (rig) {
			index = rig;
			continue;
		}
		//左右节点为空
		cout << index << " ";
		index = arr[index].parent;
		if (arr[index].left)
			arr[index].left = 0;
		else
			arr[index].right = 0;
		
		count++;
	}

	system("pause");
	return 0;
}

发表于 2019-09-10 00:45:29 回复(0)
zhangxuefeng_qq头像 zhangxuefeng_qq 
#include <iostream>
#include <locale>
#include <vector>
using namespace std;

struct TreeNode {
    int value;
    TreeNode* parent;
    TreeNode* leftChild;
    TreeNode* rightChild;
    TreeNode(){
        parent =nullptr;
        leftChild=nullptr;
        rightChild=nullptr;
    }
};
int main() {
    int n;
    cin>>n;
    vector<TreeNode> vv(n);

    for(int i =1 ; i<= n ;i++){
        vv[i-1].value = i;
        int l,r;
        cin>>l>>r;
        if(l){
            vv[i-1].leftChild = &(vv[l-1]);
            vv[l-1].parent = &(vv[i-1]);
        }
        if(r){
            vv[i-1].rightChild = &(vv[r-1]);
            vv[r-1].parent = &(vv[i-1]);
        }
    }
    // 数据读取完毕 
    TreeNode* root = &(vv[0]);//根节点
    TreeNode* cur = root;
    vector<int> ret;
    while(cur){
        ret.push_back(cur->value);
        if(cur->rightChild){
            cur = cur->rightChild;
        }
        else if(cur ->leftChild){
            cur = cur->leftChild;
        }
        else{
            TreeNode* par = cur->parent;
            while(par){
                if(par->rightChild == cur && par->leftChild!=nullptr){
                    cur = par->leftChild;
                    break;
                }
                else{
                    cur = cur->parent;
                    par = cur->parent;
                } 
            }
            if(par == nullptr){
                cur = nullptr;
            }
        }
    }
    for(int i =ret.size()-1; i > 0; i--){
        cout<<ret[i]<< " ";
    }
    cout<<ret[0]<<endl;
}
// 64 位输出请用 printf("%lld")


编辑于 2023-12-24 21:53:58 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 瓜子二手车 2019 大数据开发工程师 Java工程师
上传者：小小
难度：
2条回答 1665浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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