生活随笔
收集整理的這篇文章主要介紹了
二叉树解题套路
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1.二叉樹前序遍歷
1.1遞歸
class
Solution {
public
:vector
<int
> res
;vector
<int
> preorderTraversal(TreeNode
* root
) {dfs(root
);return res
;}void
dfs(TreeNode
*root
){if(!root
) return;res
.push_back(root
->val
);dfs(root
->left
);dfs(root
->right
);}
};
1.2棧(優(yōu)先右子樹進棧)
class
Solution {
public
:vector
<int
> preorderTraversal(TreeNode
* root
) {if(!root
) return {};stack
<TreeNode
*> sta
;sta
.push(root
);vector
<int
> res
;while(!sta
.empty()) {TreeNode
*t
=sta
.top();if(t
)res
.push_back(t
->val
);sta
.pop();if(t
->right
)sta
.push(t
->right
);if(t
->left
)sta
.push(t
->left
);}return res
;}
};
1.二叉樹的中序遍歷
2.1遞歸
class
Solution {
public
:void
inorder(TreeNode
* root
, vector
<int
>& res
) {if (!root
) {return;}inorder(root
->left
, res
);res
.push_back(root
->val
);inorder(root
->right
, res
);}vector
<int
> inorderTraversal(TreeNode
* root
) {vector
<int
> res
;inorder(root
, res
);return res
;}
};
2.2棧
class
Solution {
public
:vector
<int
> inorderTraversal(TreeNode
* root
) {vector
<int
> res
;stack
<TreeNode
*> stk
;while (root
!= nullptr
|| !stk
.empty()) {while (root
!= nullptr
) {stk
.push(root
);root
= root
->left
;}root
= stk
.top();stk
.pop();res
.push_back(root
->val
);root
= root
->right
;}return res
;}
};
3.二叉樹的后序遍歷
3.1遞歸
class
Solution {
public
:void
postorder(TreeNode
*root
, vector
<int
> &res
) {if (root
== nullptr
) {return;}postorder(root
->left
, res
);postorder(root
->right
, res
);res
.push_back(root
->val
);}vector
<int
> postorderTraversal(TreeNode
*root
) {vector
<int
> res
;postorder(root
, res
);return res
;}
};
3.2棧
class
Solution {
public
:vector
<int
> postorderTraversal(TreeNode
*root
) {vector
<int
> res
;if (root
== nullptr
) {return res
;}stack
<TreeNode
*> stk
;TreeNode
*prev
= nullptr
;while (root
!= nullptr
|| !stk
.empty()) {while (root
!= nullptr
) {stk
.emplace(root
);root
= root
->left
;}root
= stk
.top();stk
.pop();if (root
->right
== nullptr
|| root
->right
== prev
) {res
.emplace_back(root
->val
);prev
= root
;root
= nullptr
;} else {stk
.emplace(root
);root
= root
->right
;}}return res
;}
};
3.3巧妙解法
class
Solution {
public
:vector
<int
> postorderTraversal(TreeNode
* root
) {if(!root
) return {};vector
<int
> res
;stack
<TreeNode
*> postorder
;postorder
.push(root
);while(!postorder
.empty()){TreeNode
*temp
= postorder
.top();postorder
.pop();res
.push_back(temp
-> val
);if(temp
-> left
) postorder
.push(temp
-> left
);if(temp
-> right
) postorder
.push(temp
-> right
);}reverse(res
.begin(), res
.end()); return res
;}
};
4.二叉樹的層序遍歷
4.1遞歸解法
class
Solution {
public
:vector
<vector
<int
>> levelOrder(TreeNode
* root
) {vector
<vector
<int
>> res
;dfs(res
, root
, 0);return res
;}void
dfs(vector
<vector
<int
>>& res
, TreeNode
* root
, int level
) {if (!root
) return;if (level
>= res
.size())res
.push_back(vector
<int
>());res
[level
].push_back(root
->val
);dfs(res
, root
->left
, level
+ 1);dfs(res
, root
->right
, level
+ 1);}
};
4.2非遞歸解法
class
Solution {
public
:vector
<vector
<int
>> levelOrder(TreeNode
* root
) {vector
<vector
<int
>> ret
;if (!root
) {return ret
;}queue
<TreeNode
*> q
;q
.push(root
);while (!q
.empty()) {int currentLevelSize
= q
.size();ret
.push_back(vector
<int
> ());for (int i
= 1; i
<= currentLevelSize
; ++i
) {auto node
= q
.front(); q
.pop();ret
.back().push_back(node
->val
);if (node
->left
) q
.push(node
->left
);if (node
->right
) q
.push(node
->right
);}}return ret
;}
};
總結(jié)
以上是生活随笔為你收集整理的二叉树解题套路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
