代码随想录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;}
};

对称二叉树

迭代法两两取出元素判断

1. 左左边和右右边，左右边和右左边判断
2. 注意空指针的判断，if(!leftNode || !rightNode || (leftNode->val != rightNode->val))
3. 左和右同时是空的也要判断哦，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;}
};