【LeetCode 热题 100】二叉树 系列

📁 104. 二叉树的最大深度

        深度就是树的高度，即只要左右子树其中有一个不为空，就继续往下递归，知道节点为空，向上返回。

int maxDepth(TreeNode* root) {if(root == nullptr)return 0;return max(maxDepth(root->left) , maxDepth(root->right)) + 1;}

📁 94. 二叉树的中序遍历

        中序遍历就是先访问左子树，再访问根节点，最后访问右子树。

class Solution {
public:vector<int> ans;vector<int> inorderTraversal(TreeNode* root) {dfs(root);    return ans;}void dfs(TreeNode* root){if(root == nullptr)return ;dfs(root->left);ans.push_back(root->val);dfs(root->right);}
};

📁 226. 翻转二叉树

        对二叉树来一遍后序遍历，即先将左右子树翻转，保存反转后的左右子树的根节点，让root左右子树指针分别指向右子树，左子树。

TreeNode* invertTree(TreeNode* root) {if(root == nullptr)return root;TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->right = left;root->left = right;return root;}

📁 101. 对称二叉树

        求对称二叉树，我们只需要判断左右子树是否满足满足下面这些性质：1. 左右子树根节点相同；2. 左子树的右子树 = 右子树的的左子树；3. 左子树的左子树 = 右子树的右子树。

    bool isSymmetric(TreeNode* root) {return isSameTree(root->left , root->right);}bool isSameTree(TreeNode* t1 , TreeNode* t2){if(t1 == nullptr && t2 == nullptr)return true;if(t1 == nullptr || t2 == nullptr)return false;if(t1->val != t2->val)return false;return isSameTree(t1->left , t2->right) && isSameTree(t1->right , t2->left);}

📁 543. 二叉树的直径

        以某个节点为根节点，统计做左子树的最长路径，在统计右子树的最长路径，左右子树最长路径相加就是该二叉树的直径。

        递归函数向上返回该二叉树的最长路径。

    int ans = 0;int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans;}int depth(TreeNode* root){if(root == nullptr)return 0;int left = depth(root->left);int right = depth(root->right);ans = max(ans , left + right);return max(left , right) + 1;}

📁 102. 二叉树的层序遍历

        我们使用队列来完成二叉树的层序遍历，利用队列 [先入先出]的特性，将每一层的节点入队列，出队列按一层节点个数出队列。

        如果出队列的每一个节点左右子树指针还有节点，在入队列，因为之前已经确定好了每一层节点个数，因此出队列时不回影响新入队列的节点。

vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr)return vector<vector<int>>();vector<vector<int>> ret;            queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> tmp;   //记录该层每一个节点的值int sz = q.size(); //记录该层的节点个数for(int i = 0 ; i < sz ; ++i){   TreeNode* node = q.front();q.pop();tmp.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}ret.push_back(tmp);}return ret;}

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

        二叉搜索树的特征就是，左子树所有节点的值都小于根节点的值，右子树所有节点的值都大于根节点的值；对二叉搜索树进行前序遍历得到的结果是一个有序数组。

        对于本题，我们就可以采用二分+前序递归的方法，将中间值mid作为根节点，比mid小的放在左子树，比mid大的放在右子树。

TreeNode* dfs(vector<int>& nums , int left , int right){if(left > right)return nullptr;int mid = (left + right) >> 1;TreeNode* node = new TreeNode(nums[mid]);node->left = dfs(nums , left , mid - 1);node->right = dfs(nums , mid + 1 , right);return node;}TreeNode* sortedArrayToBST(vector<int>& nums) {return dfs(nums , 0 , nums.size() - 1);}

📁 98. 验证二叉搜索树

        二叉搜索树的特征就是，左子树所有节点的值都小于根节点的值，右子树所有节点的值都大于根节点的值；对二叉搜索树进行前序遍历得到的结果是一个有序数组。

        根绝二叉树性质我们可以知道，对二叉树进行前序遍历时，root节点的值一定大于上一个已经被遍历的节点值（左子树中最右节点）prev。

        递归函数返回值为是否为二叉搜索树，先遍历左子树是否二叉搜索树，在判断根节点值是否大于prev，然后在判断右子树是否是二叉搜索树。

        特殊情况：初始化prev值为最小值；如果是空间点nullptr，返回值为true。

long prev = LONG_MIN;bool dfs(TreeNode* root){if(root == nullptr)return true;bool left = dfs(root->left);if(!left)return false;if(root->val <= prev)return false;prev = root->val;bool right = dfs(root->right);return right;}bool isValidBST(TreeNode* root) {return dfs(root);        }

📁 230. 二叉搜索树中第 K 小的元素

        从左往右递归，即前序遍历，依次--k，知道找到k为0的节点，这就是第k小的元素节点。

class Solution {
public:int count = 1;int ret = 0;int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ret;    }void dfs(TreeNode* root){if(root == nullptr)return ;dfs(root->left);count--;if(count == 0){ret = root->val;return ;}dfs(root->right);}
};

📁 199. 二叉树的右视图

        l利用BFS进行层序遍历，记录下来每一层的最后一个节点元素即可。

class Solution {
public:vector<int> ret;vector<int> rightSideView(TreeNode* root) {if(root == nullptr)return vector<int>();queue<TreeNode*> q;q.push(root);while(!q.empty()){int sz = q.size();for(int i = 0 ; i < sz; ++i){TreeNode* node = q.front(); q.pop();if(node->left)q.push(node->left);if(node->right)q.push(node->right);if(i == sz - 1)ret.push_back(node->val);}}return ret;    }
};

📁 114. 二叉树展开为链表

        判断左子树是否为空，如果为空，当前节点root不需要展开，已经展开为链表，处理当前节点的右子树。

        如果不为空，需要找到左子树的最右节点作为右子树的根节点的前驱节点，当前节点root->left值为nullptr，右子树为左子树的根节点，处理完当前层后展开为链表，然后处理右子树。

class Solution {
public:void flatten(TreeNode* root) {TreeNode* cur = root;while(cur){if(cur->left){TreeNode* left = cur->left;TreeNode* prev = left;while(prev->right)prev = prev->right;prev->right = cur->right;cur->right = left;cur->left = nullptr;}cur = cur->right;}}
};

📁 105. 从前序与中序遍历序列构造二叉树

       本题默认是所有值不重复

        前序遍历的第一个节点一定是根节点，我们在中序遍历中查找根节点，即可找到左子树和右子树。

        因此，递归遍历拿到prev中第一个节点一定是根节点，创建根节点，递归创建左子树根节点，在递归创建右子树根节点，直到数组中没有数据再能创建节点。

        我们在中序遍历中找到根节点，就能知道左子树长度和右子树长度，我们采用空间换时间的方法，记录下来中序遍历中每个节点对应的下标。

class Solution {
public:unordered_map<int,int> index;TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder , int prev_left , int prev_right,int in_left , int in_rihgt){if(prev_left > prev_right || in_left > in_rihgt)return nullptr;//记录前序遍历中root的下标 以及中序遍历中root的下标int in_root = index[preorder[prev_left]];//新建节点TreeNode* root = new TreeNode(preorder[prev_left]);//记录左子树的个数int sz = in_root - in_left;root->left = myBuildTree(preorder , inorder , prev_left + 1 , prev_left + sz, in_left , in_root - 1);root->right = myBuildTree(preorder , inorder , prev_left + 1 + sz , prev_right, in_root + 1 , in_rihgt);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int sz = preorder.size();for(int i = 0 ; i < sz ; ++i)index[inorder[i]] = i;return myBuildTree(preorder , inorder , 0 , sz - 1 , 0 , sz - 1);}
};

📁 437. 路径总和 III

        我们采用前缀和的方法，从根节点开始，不断地往某一分支+root->val值为cur，如果满足公式：targetNum + ? = cur，如果 ？ 存在，就表明上述公式成立，targetNum一定存在，ans += 齐前缀和为 ？的个数。

        步骤：判断从当前节点往上是否满足公式，如果满足，ans += 前缀和为 ？的个数；在判断左右子树，即ans += 左右子树中满足公式的前缀和的个数。

class Solution {
public:unordered_map<long long , long long> hash;int pathSum(TreeNode* root, int targetSum) {hash[0] = 1;return dfs(root , 0 , targetSum);}int dfs(TreeNode* root , long long cur ,long long targetSum){if(root == nullptr)return 0;int ans = 0;cur += root->val;if(hash.find(cur - targetSum) != hash.end())ans += hash[cur - targetSum];hash[cur]++;ans += dfs(root->left , cur , targetSum);ans += dfs(root->right , cur , targetSum);hash[cur]--;return ans; }
};

📁 236. 二叉树的最近公共祖先

        分为以下三种情况，递归查找p节点和q节点，如果找到向上返回，如果没有返回nullptr，分别查找左右子树。

        1. 如果左右子树递归结果为空，说明没有找到p，q节点，返回nullptr。

        2. 如果左子树为空，说明p和q节点在右子树中，p或q节点为另一个节点的最近公共祖先。

        3. 右子树为空，同理可得。

        4. 如果左右子树都不为空，说明此时，root为p和q的最近公共祖先。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr || root == p || root == q)return root;TreeNode* left = lowestCommonAncestor(root->left , p , q);TreeNode* right = lowestCommonAncestor(root->right , p , q);if(!left)return right;if(!right)return left;return root;}
};

📁 124. 二叉树中的最大路径和

        本题，我们采用后序遍历的思路，先查找左子树中最大值的路径，最查找右子树中最大值的路径，然后+上根节点的值，记录下来最大值即可。

        返回值为，从根节点开始，到左右子树中找到一条值最大的路径，向上返回该路径的值+根节点的值。

        递归结束条件就是找到叶子节点，向上返回。

class Solution {
public:int ret = INT_MIN;int maxPathSum(TreeNode* root) {dfs(root);return ret;    }int dfs(TreeNode* root){if(root == nullptr)return 0;int left = max(0 , dfs(root->left));int right = max(0 , dfs(root->right));ret = max(ret , root->val + left + right);return root->val + max(left , right);}
};