代码随想录day14

二叉树的反转，采用迭代，只能用前序和后序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==NULL) return root;invertTree(root->left);//左 invertTree(root->right);//右swap(root->left,root->right);//中return root;}
};

二叉树是否对称,采用后序遍历，左右中，判断根节点两个子树是否相等

1.先判断是否空，再判断数值是否相等

2.如果可以，判断子树里侧和外侧是否相等

二叉树的最大深度

深度指的是根节点到叶子节点的距离，从1开始，前序遍历，中左右

高度是从叶子节点到根节点的距离，后序遍历，左右中

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getdepth(TreeNode *node){if(node==NULL) return 0;int leftdep=getdepth(node->left);int rightdep=getdepth(node->right);int depth=1+max(leftdep,rightdep);return depth;}int maxDepth(TreeNode* root) {int depth= getdepth(root);return depth;}
};

二叉树的最小深度，

叶子节点是左右孩子都为空，根节点到叶子节点的最小距离

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getdep(TreeNode* node){if(node==NULL)  return 0;int leftdep=getdep(node->left);int rightdep=getdep(node->right);
//如果左孩子为空，说明不是叶子节点，返回右深度if(node->left==NULL&&node->right!=NULL){  return 1+rightdep;}if(node->left!=NULL&&node->right==NULL)   return 1+leftdep;int res= 1+min(leftdep,rightdep);return res;}int minDepth(TreeNode* root) {return  getdep(root);}
};