leetcode hot100 二叉树（一）

1.二叉树的中序遍历

        中序遍历（中根遍历）：左-根-右顺序，递归实现。注意设置递归终止条件。

class Solution {
public:void search(TreeNode* root,vector<int>& ans){if(!root) return ;search(root->left,ans);ans.push_back(root->val);search(root->right,ans);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(!root) return res;search(root,res);return res;}
};

2.二叉树的最大深度

        max（左子树深度，右子树深度）+1（根节点本身占一个深度）

class Solution {
public:int maxDepth(TreeNode* root) {if(!root) return 0;return max(maxDepth(root->left)+1,maxDepth(root->right)+1);}
};

3.翻转二叉树

• 后序遍历：采用后序遍历（左右根）的方式，先处理子节点再处理父节点
• 自底向上：从底层开始往上一点一点交换

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(!root) return nullptr;//从底层开始往上一点一点换TreeNode* left=invertTree(root->left);TreeNode* right=invertTree(root->right);root->left=right;root->right=left;return root;}
};

4.对称二叉树

• 结构上的不对称直接剪枝处理：

         左子树还有但右子树没了/左子树没了但右子树还有-->结构上就不可能对称，可以直接剪枝。

• 除了以上情况外，正常递归判断：

          要求r1->val==r2->val、judge(r1->right,r2->left)且judge(r1->left,r2->right)。

class Solution {
public:bool isSymmetric(TreeNode* root) {return judge(root->left,root->right);}bool judge(TreeNode *r1,TreeNode*r2){if(!r1&&!r2) return true;if(!r1||!r2) return false;return r1->val==r2->val&&judge(r1->right,r2->left)&&judge(r1->left,r2->right);}
};

5.二叉树的直径

思路：遍历到每个结点时，递归其左子树高度与右子树高度之和，并不断更新最大直径len。

注意：直径不一定经过根节点。

class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int len=0;calculate(root,len);return len;}int calculate(TreeNode* root,int& len){if(!root) return 0;int left_height=calculate(root->left,len);int right_height=calculate(root->right,len);len=max(len,left_height+right_height);  //在计算高度的同时，记录"左高度 + 右高度"的最大值。return max(left_height,right_height)+1;}
};

6.二叉树的层序遍历

• 类似bfs算法，但引入sz变量记录每层结点数，每一层单独存放为一个vector
• 处理每层结点的同时将该结点的左孩子和右孩子push_back进vector里

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(!root) return res;queue<TreeNode*> q;q.push(root);while(q.size()){int sz=q.size();vector<int> curr;for(int i=0;i<sz;i++){auto t=q.front();q.pop();curr.push_back(t->val);if(t->left) q.push(t->left); if(t->right) q.push(t->right);}res.push_back(curr);  //每遍历一层push_back一次数组}return res;}
};

 7.将有序数组转换为二叉搜索树

核心思想：利用二分查找的策略进行递归建树（有序数组和二叉搜索树都是二分查找时的常用结构，因此可以利用二分思想从中间结点开始递归创建左右子树）

class Solution {
public:TreeNode* buildTree(vector<int>& nums,int l,int r){if(l>r) return nullptr;int mid=(l+r)>>1;TreeNode* root=new TreeNode(nums[mid]);root->left=buildTree(nums,l,mid-1);  //递归创建左子树root->right=buildTree(nums,mid+1,r);  //递归创建右子树return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return buildTree(nums,0,nums.size()-1);}
};