本文主要是介绍代码随想录day 14:第六章 二叉树 part02,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
翻转二叉树
原则:其实只需要代码能访问到每一个节点,然后swap左右孩子就好了.
递归法
用递归的思想来深度遍历访问每个节点,然后swap每个访问到的节点
class Solution {
public:void traversal(TreeNode* cur){if(cur==NULL) return;swap(cur->left,cur->right);traversal(cur->left);traversal(cur->right);}TreeNode* invertTree(TreeNode* root) {traversal(root);return root;}
};
深度优先
用前中后序的深度遍历方式栈的遍历方式,以下是前序。
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*>st;if(root!=NULL){st.push(root);}else{return root;}while(!st.empty()){TreeNode* node = st.top();swap(node->left, node->right);st.pop();if(node->left) st.push(node->left);if(node->right) st.push(node->right);}return root;}
};
层序遍历
遍历每一个节点然后交换其左右孩子即可
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();swap(node->left, node->right); // 节点处理if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return root;}
};
对称二叉树
迭代法两两取出元素判断
- 左左边和右右边,左右边和右左边判断
- 注意空指针的判断,if(!leftNode || !rightNode || (leftNode->val != rightNode->val))
- 左和右同时是空的也要判断哦,continue
class Solution {
public:bool isSymmetric(TreeNode* root) {if(root==NULL){return true;}queue<TreeNode*>que;que.push(root->left);que.push(root->right);while(!que.empty()){TreeNode* leftNode = que.front();que.pop();TreeNode* rightNode = que.front();que.pop();if(!leftNode && !rightNode){continue;}if(!leftNode || !rightNode || (leftNode->val != rightNode->val)){return false;}que.push(leftNode->left);que.push(rightNode->right);que.push(leftNode->right);que.push(rightNode->left);}return true;}
};
二叉树的最大深度
用迭代法好理解点
就是每遍历一层深度就+1
class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*>que;if(root==NULL) return 0;int depth = 0;que.push(root);while(!que.empty()){int size = que.size();depth++;for(int i=0; i<size;i++){TreeNode* node = que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return depth;}
};
二叉树的最小深度
依然用层序遍历快点,并且关键判断左右子树为空就行了
class Solution {
public:int minDepth(TreeNode* root) {if(root == NULL) return 0;queue<TreeNode*>que;int depth = 0;que.push(root);while(!que.empty()){int size = que.size();depth++;for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();if(!node->left && !node->right){return depth;}if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return depth;}
};
这篇关于代码随想录day 14:第六章 二叉树 part02的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!