題目：二叉樹的后序遍歷
給定一個二叉樹，回傳它的 后序 遍歷。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
代碼如下：
//莫里斯遍歷
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void addPath(int *res, int *returnSize, struct TreeNode *root) { //主要是這個函式沒看懂，這個函式的作用是什么？
int count = 0;
while (root != NULL) {
++count;
res[(*returnSize)++] = root->val;
root = root->right;
}
for (int i = (*returnSize) - count, j = (*returnSize) - 1; i < j; ++i, --j) {
int t = res[i];
res[i] = res[j];
res[j] = t;
}
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = 0;
int *res = malloc(sizeof(int)*100);
struct TreeNode *p = NULL;
struct TreeNode *temp = root;
while (temp){
if (temp->left){
p = temp->left;
while (p->right!=NULL && p->right!=temp){
p = p->right;
}
if (p->right==NULL){
p->right = temp;
temp = temp->left;
}
else{
p->right = NULL;
addPath(res, returnSize, temp->left); //這個函式為什么要放在這里？
temp = temp->right;
}
}
else{
temp = temp->right;
}
}
addPath(res, returnSize, root);
return res;
}
uj5u.com熱心網友回復：
大佬們，我發現二叉樹的后序遍歷的非遞回代碼相比前序遍歷和中序遍歷，很不好理解，有什么訣竅嗎？
uj5u.com熱心網友回復：
其實說好理解也好理解，說不好理解也不好理解，前中后序只是列印的地方不同，遍歷程序是相同的。就像上次跟你說的，它的遍歷程序就是先找到左子樹的最右節點，然后讓最右節點的右節點指向父節點，然后父節點的左子樹繼續遍歷，當遍歷到最右節點的右節點就會回到父節點（因為之前設定了最右節點的右節點指向父節點），然后恢復最右節點的右節點為NULL，并遍歷父節點的右子樹。
所以前中后序的差別上只是在于什么時候列印。
后序列印為什么會復雜呢？因為它要遍歷到最右節點才開始列印（前序，中序在中間就列印），所以它要遍歷到最右節點以后，才開始逆向列印之前的各層的節點。那么怎么逆向列印呢？想想還不簡單嗎？因為遍歷到最右節點時，最右節點的右節點又回到了父節點，拿到父節點，就可以得到原來的父節點的左右節點。
所以addPath就是為了列印這個從最右節點開始逆向遍歷的結果。
先順著列印
res[(*returnSize)++] = root->val;
root = root->right;
再逆向重新排列結果
int t = res[i];
res[i] = res[j];
res[j] = t;
這里的逆序addPath可能用了技巧，只需要對半逆向，具體沒太細研究，大體思路就是這樣，所以后序需要找到最右才能開始列印，不像前序中序在遍歷程序中就能列印，所以它比較繁瑣。
這種技巧性的東西，我覺得沒有必要研究得太深，意義不大，可能只是一開始驚嘆一下這技巧不錯，但是不能給其他問題帶來什么新的啟發，所以大概了解就可以了。
uj5u.com熱心網友回復：
十分感謝，我感覺二叉樹代碼好長，有點不好理解，但理解過后就發現其實二叉樹就是鏈表，想想前面剛學鏈表時還挺輕松的，真讓我郁悶
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/159480.html
標籤：C語言
下一篇：農夫過河問題