94.二叉樹的中序遍歷

給定一個二叉樹的根節點?root?，返回?它的?中序?遍歷?。

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

• 樹中節點數目在范圍?[0, 100]?內
• -100 <= Node.val <= 100

進階:?遞歸算法很簡單，你可以通過迭代算法完成嗎？

思路：類似于我們之前講過的遞歸算法中序遍歷二叉樹：二叉樹的遍歷

? ? ? ? 這里我們需要返回的是數組，數組中的元素是按照中序遍歷的順序，同時返回數組的大小，也就意味著我們需要先計算二叉樹的大小，該方法我們在二叉樹的遍歷中同樣也實現了

代碼實現：

int TreeSize(struct TreeNode* root){if(!root){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);
}void Inorder(struct TreeNode* root,int*arr,int* index){if(!root){return;}Inorder(root->left,arr,index);arr[*index]=root->val;(*index)++;Inorder(root->right,arr,index);
}int* inorderTraversal(struct TreeNode* root, int* returnSize){if(!root){* returnSize = 0;return NULL;} int size = TreeSize(root);* returnSize = size;int* arr = (int*)malloc(sizeof(int)*size);int index = 0;Inorder(root,arr,&index);return arr;
}

145. 二叉樹的后序遍歷

---

145. 二叉樹的后序遍歷

給你一棵二叉樹的根節點?root?，返回其節點值的?后序遍歷?。

示例 1：

輸入：root = [1,null,2,3]

輸出：[3,2,1]

解釋：

示例 2：

輸入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

輸出：[4,6,7,5,2,9,8,3,1]

解釋：

示例 3：

輸入：root = []

輸出：[]

示例 4：

輸入：root = [1]

輸出：[1]

提示：

• 樹中節點的數目在范圍?[0, 100]?內
• -100 <= Node.val <= 100

算法思路：與我們的中序遍歷一樣：思路同樣參考二叉樹的遍歷

代碼實現如下：

int TreeSize(struct TreeNode* root){if(!root){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);
}void PostOrder(struct TreeNode* root,int*arr,int* index){if(!root){return;}PostOrder(root->left,arr,index);PostOrder(root->right,arr,index);arr[*index]=root->val;(*index)++;
}int* postorderTraversal(struct TreeNode* root, int* returnSize){if(!root){* returnSize = 0;return NULL;} int size = TreeSize(root);* returnSize = size;int* arr = (int*)malloc(sizeof(int)*size);int index = 0;PostOrder(root,arr,&index);return arr;
}

好了，本期關于二叉樹的遍歷就到這里結束了，相信大家對于二叉樹的遍歷已經十分得心應手了，這里遞歸的思想非常重要，但是對于那些比較大的樹，深樹，遞歸的方式往往容易棧溢出。我們會采取迭代加棧與隊列以及層序的方式來完成--這些內容會留到c++部分進行講解。謝謝大家的點贊和收藏！！