周末说说二叉树之重构

﹏ヽ暗。殇╰゛Y 2022-12-10 11:29 82阅读 0赞

老师在讲这个根据前序，中序的结果重建二叉树的时候，事实上是给出了流程图的，但递归的方法更简单：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70_pic_center]  
然后看看left和right的构造就行了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70_pic_center 1]

那么代码是不是也很简单呢：

struct node *rebuild(int *Preorder, int *Inorder, int StartPre, int EndPre, int StartMid, int EndMid)
    { 
    	struct node *root;
    	int distance;
    
    	if (StartPre > EndPre || StartMid > EndMid) { 
    		return NULL;
    	}
    	
    	for (distance = 0; distance < EndMid; distance++) { 
    		if (Inorder[StartMid + distance] == Preorder[StartPre]) { 
    			break;
    		}
    	}
    
    	root = (struct node *)malloc(sizeof(struct node));
    	root->val = Preoder[StartPre];
    	root->left = rebuild(Preorder, Inorder, StartPre + 1, StartPre + distance, StartMid, distance - 1);
    	root->right = rebuild(Preorder, Inorder, StartPre + distance + 1, EndPre, distance + 1, EndMid);
    
    	return root;
    	
    }

还有不到一个半月就要软考了，三个月前我报了个软考培训班，身边的同事朋友们都笑我，觉得这个没有意义很low逼，我并不这么认为，饱汉不知饿汉饥，作为一个不会编程的手艺人，任何培训都是一个梳理知识体系的机会，此外，我并非科班，又是个大专，大家认为理所当然的东西可能在我这里就是个空白，所以我并不认为这没有意义。我必须抓住一切机会，抓住任何渠道，不断学习。

此外，在这个高度内卷的时代，没有学历，退休以后是拿不到国家承诺的退休金的，证书多拿一个是一个，虽大势上于事无补，多一分钱是一分钱吧。

在这个培训中，我觉得关系代数这个比较有趣，我之前没接触过这个领域，这也算弥补了我的一个知识空白，此外就是数据结构了，本文就是其中一例。

--------------------

浙江温州皮鞋湿，下雨进水不会胖。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7996d0f3826348579661755e41ac106c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/735ac1a40ff84f70ab18c054eb0bd6e0.png