題目:94. 二叉樹的中序周遊
給定一個二叉樹,傳回它的中序 周遊。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
進階: 遞歸算法很簡單,你可以通過疊代算法完成嗎?
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
題解
樹一種特殊的圖,是連通的,無回路的無向圖。
是以,二叉樹的搜尋也稱二叉樹的周遊,同樣有深度優先周遊和廣度優先周遊兩種方式。
廣度優先周遊也稱為層序周遊,周遊原則為:以樹的根節點開始,按照樹的高度由低到高,一層一層地周遊下去,每一層按照從左至右的順序周遊,直至到達樹的最大深度,周遊完全部節點為止。
深度優先周遊,周遊原則為:從樹的根節點開始,沿着左子樹進行深度周遊,直到到達葉子節點為止;然後回溯到根節點,進行右子樹的深度周遊,直到周遊完所有節點。
具體的,按照根節點相對于子節點的通路順序,可進一步分為前序周遊、中序周遊和後序周遊。
這裡固定左節點和右節點的周遊順序,那麼:
前序(pre-order)指先通路根節點,再周遊左子樹和右子樹;
中序(in-order)是指先周遊左子樹,接着通路根節點,最後周遊右子樹;
後序(post-order)是指先周遊左子樹,接着周遊右子樹,最後通路根節點。
代碼
遞歸
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
inorder(root, ans);
return ans;
}
void inorder(TreeNode* node, vector<int>& ans) {
if (node == NULL) {
return;
}
inorder(node->left, ans);
ans.push_back(node->val);
inorder(node->right, ans);
}
};
棧的疊代
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
while (root or !stk.empty()) {
while (root != NULL) {
stk.push(root);
root = root->left;
//沿着根節點及左子樹這條路徑周遊到底,并将節點放入棧中
}
//通路根節點及左子樹這條路徑上的節點
TreeNode* node = stk.top();
stk.pop();
ans.push_back(node->val);
//按照同樣的政策,深度周遊右子樹
root = node->right;
}
return ans;
}
};