生活随笔
收集整理的这篇文章主要介绍了
二叉树解题套路
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
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栈(优先右子树进栈)
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
;}
};
总结
以上是生活随笔为你收集整理的二叉树解题套路的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
