[数据结构与算法] LeetCode-树专题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode-树专题 -> 正文阅读

[数据结构与算法]LeetCode-树专题

树
树是链表结构的扩展，因为链表只有一个分叉，遍历的时候方便遍历。树分两个叉，遍历的时候用递归的方式。

树为什么适合用递归写法？因为树天然具有递归的性质，子树的性质和整个树的性质一致，使用递归可以轻松地将整个树问题转换成子树问题。当层层递归到最小子树时，这个最小子树的解(也称为递归出口)往往很容易得到，然后再一步步回溯就能得到原问题的解。

树递归的思路：归纳成一个子问题
① 写出子问题的推导
② 写出终止条件

树的前/中/后序遍历
自顶向下->前序遍历：在每个递归层级上首先访问节点来计算一些值；并在递归调用函数时将这些值通过参数传递到子树中
自底向上->后序遍历：首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。依赖左右子树的返回值
中序遍历

什么时候用前中后序遍历呢？
1、如果能使用参数和节点本身的值来决定应该传递给它的子节点的参数，就用前序遍历
2、对于树中的任意一个节点，如果知道它子节点的答案，就能计算出当前节点的答案，就用后序遍历
3、如果遇到二叉搜索树就用中序遍历

树递归最简公式：
1、归纳成子问题，写出子问题的推导
2、终止条件

104 二叉树的最大深度
归纳成一个子问题：一棵树的最大深度 = 左子树和右子树的深度最大的那个+1（子问题的推导）
终止条件

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0; // 终止条件，这样就可以依次对外返回，得到整棵树的深度
        int maxleft = maxDepth(root->left);
        int maxright = maxDepth(root->right);
        return max(maxleft, maxright) + 1;
    }
};

226 翻转二叉树
递归子问题：
直接翻转左右节点：swap(root->left, root->right); // 该节点的左右节点翻转过来了，如果只执行这个代码，对应于下图中只会2和7掉个，下面的不会掉个。
故，要递归地调用invertTree，将左右子树也掉个
swap(invertTree(root->left), invertTree(root->right))，逻辑：左子树反转，右子树反转，然后再将其反转

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

二叉树的前中后序遍历（遍历一整棵树的结构代码）
二叉树的存储是链式存储，链表中查找某点需要从头结点遍历，故二叉树的遍历也需要从根节点遍历（链表的头指针指向二叉树的根节点）。
树结构遍历顺序：遍历当前节点，再遍历左节点和右节点

// 什么时候处理TreeNode 对应着二叉树不同的遍历方式
function walk(TreeNode)
{
    // 终止条件
    if (!TreeNode) return;
        
    // 前序遍历
    处理treeNode; // 进入节点，主逻辑
    walk(treeNode->left);
    walk(treeNode->right);

    // 中序遍历
    walk(treeNode->left);
    处理treeNode; // 主逻辑
    walk(treeNode->right);

    后序遍历
    walk(treeNode->left);
    walk(treeNode->right);
    处理treeNode; // 离开节点，主逻辑
}

144 二叉树的前序遍历

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;
        res.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
};

二叉树前序遍历迭代写法
1、需要一个栈
2、每次遍历栈时：
每次都扣出来一个
进行处理
将其左右节点推进栈中（这样就会不停的遍历栈）

// 输入没有空，
// 输入：root = []：表示数组长度为0，输出：[]：表示返回一个空数组

class Solution {
public:
    vector<int> res;
    stack<TreeNode*> stk;
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return res; // 这个可以省略，因为输入没有空节点
        stk.push(root);
        while (stk.size())
        {
            auto t = stk.top();
            stk.pop();
            res.push_back(t->val);
            if (t->right) stk.push(t->right); // 注意先放右节点，再放左节点
            if (t->left) stk.push(t->left);
        }
        return res;
    }
};

94 二叉树的中序遍历

// 递归写法
class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }
};

// 迭代写法

145 二叉树的后序遍历

class Solution {
public:
    vector<int> res;

    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }
};

100 相同的树
逻辑：判断两个树当前节点的值是否相等，如果相等，两棵树的 left和两棵树的 right是否相等

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 相同：1、在结构上相同   2、节点值相同
        
        // 下面3个if是不需要进行递归的逻辑
        // 1、提前预判：如果两个都是NULL，就不用参与树型判断的逻辑。2、在递归的时候如果递归到两个子树都是NULL也认为相等
        if (p == NULL && q == NULL) return true; 
        // 如果两个不全是NULL，两个都是NULL情况上面已经处理过，如果有一个是NULL，另外一个不是NULL。
        if (p == NULL || q == NULL) return false;
        // 先判断不相等，为什么？因为它俩值相等的情况下需要进行递归，两个节点相等并不代表两个树相等，还需要深入到底层看其子元素是否相等
        if (p->val != q->val) return false;
        // 两个节点值一样，需要递归的判断
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

101 对称二叉树

比较的不是左右节点，而是左右子树，所以在递归遍历的过程中，也需要同时遍历这两棵树
思路：考虑的时候一般先考虑的是一个局部信息(最小的子树，此题中最小的子树是3个节点的子树)

求的时候我们只需要考虑如何维护这些信息即可：要求当前树是否为对称二叉树，考虑它的左右子树是否是对称二叉树，如果左右子树都是对称二叉树，那么当前树就是对称二叉树。假设以u为根节点的树是否为对称二叉树记为f(u)，要考虑的就是f(u)与f(a)和f(b)的关系，一般只需要考虑这样一个局部信息即可，只要捋清楚f(u)与f(a)和f(b)之间的关系，则可以递归地求出来每一个f(u)，f(root)就是答案。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* p, TreeNode* q)
    {
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;
        if (p->val != q->val) return false;
        // 判断对称：值相等并且子元素满足关系
        return dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

111 二叉树的最小深度
注意：需要判断如果没有左子树和右子树的单独没有的情况，要不遇到这种情况的话得到的答案都是1

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return 1;
        if (root->left == NULL) return minDepth(root->right) + 1;
        if (root->right == NULL) return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

617 合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return NULL;
        if (!root1) return root2;
        if (!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right  = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

236 二叉树的最近公共祖先
不停地向上查找，直到找到一个交叉的地方->判断当前节点，当前的节点不停往下找（遍历每一个节点），

如果两边都找到了，那么一边一个p和q，或者同时在左边或右边
① p和q有嵌套关系
② p和q没有嵌套关系

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (root == p || root == q) return root; // 如果p或q有一个是根节点(p和q有嵌套关系)就不用查找了，直接预判了
        auto left = lowestCommonAncestor(root->left, p, q); // 在左子树找p和q，
        auto right = lowestCommonAncestor(root->right, p, q); // 在右子树找p和q，
        if (left && right) return root; // 因为题目规定定义两个节点都在，如果左右子树都找到了，那一定是一边一个，那最近公共祖先就是当前的root
        return left ? left : right; // 如果p和q都在左边或者都在右边（哟嵌套关系）
    }
};

572 另一棵树的子树
不停地比较root中的某一个子树和subRoot是否相同

// 平级对比和递归嵌套的层级去对比
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;
        if (root->val == subRoot->val) // 有子树的可能性继续递归比较
        {
            if (isSameTree(root, subRoot)) return true; // 这块不能直接return isSameTree
        }
        // 如果不是的话，需要判断它的子树
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        if (!p && !q) return true;
        if (!p || !q) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

257 二叉树的所有路径 **
前序遍历，在进入节点的时候进行操作
注意：遍历节点（进入和离开）和操作节点是两个逻辑
前中后序遍历的方式都是深度优先遍历，对应不同时刻进行处理**当前节点，对应着前中后序三种不同的方式

class Solution {
public:
    vector<string> res;
    vector<int> path;
    vector<string> binaryTreePaths(TreeNode* root) {
        if (root) dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        path.push_back(root->val);

        if (!root->left && !root->right)
        {
            string line = to_string(path[0]);
            for (int i = 1; i < path.size(); i ++)
            {
                line += "->" + to_string(path[i]);
            }
            res.push_back(line);
        }

        if (root->left)
        {
            dfs(root->left);
            // path.pop_back();
        }
        if (root->right)
        {
            dfs(root->right);
            // path.pop_back();
        }
        path.pop_back();
    }
};

112 路径总和
自定向下，前序遍历+参数扩展；在向下递归的时候同时更新参数，当达到叶子节点是判断是否满足条件。
后序遍历：即在递归函数返回时对问题进行求解，使用子树的返回值来计算当前节点的值。

搜索这个二叉树的不同路径，如果找到一条符合条件的路径就返回True，如果所有路径都不复合要求就返回false

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        targetSum -= root->val;
        if (!root->left && !root->right)
            return !targetSum;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

113 路径总和II
与上一题的区别是要找到所有复合条件的路径，上一题只需要判断是否存在一条符合条件的路径

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root) dfs(root, targetSum);
        return res;
    }

    void dfs(TreeNode* root, int targetSum)
    {
        targetSum -= root->val;
        path.push_back(root->val);
        if (!root->left && !root->right && !targetSum)
            res.push_back(path);

        // 如果到达叶子节点的话下面这两个条件不会执行
        if (root->left) dfs(root->left, targetSum);
        if (root->right) dfs(root->right, targetSum);
        path.pop_back();
    }
};

543 二叉树的直径
从下往上走，用后序遍历，先遍历左右再处理自己

class Solution {
public:
    int len = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return len;
    }

    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        len = max(len, left + right);

        return max(left, right) + 1;
    }
};

124 二叉树中的最大路径和
首先明确路径的定义：路径被定义成一条从树中任意节点出发并达到任意节点的序列，该路径至少包含一个节点，且不一定经过根节点
可以用同种逻辑处理问题及其子问题的情况，使用递归思想

先思考只有三个点的最简单的情况(子树)
如果上面的这个子树是整个树的一部分
①：整个树的最大路径和就在这个子树当中，不再经过这个子树外的其它节点，最终结果 a + b + c
②：最大路径和包含节点a，并且通过a扩展到子树外的其它节点，最终结果 max(b, c) + a + parent(a)，parent(a)表示节点a往外延伸的剩余部分的路径和
③：不包含子树a
抽象：将节点b,c抽象成任意一个子树的左右子树

设定一个全局变量存储最大路径和，不断递归搜索每个子树更新该变量
1、搜索最左边的最小子树，不断回溯到更大一点的子树，直到root节点的整个子树被搜索完
2、然后对root节点的右子树做同样操作
3、判断包含root节点的情况

class Solution {
public:
    int res;
    int maxPathSum(TreeNode* root) {
        res = INT_MIN;
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        // 如果下面是负数就不用取了，故和0取max
        int left = max(0, dfs(root->left)), right = max(0, dfs(root->right));
        res = max(res, root->val + left + right);

        return root->val + max(left, right);
    }
};

将所有路径都枚举出来，然后将最值求出来。在树中枚举路径的常用方式，枚举这个路径的最高点，枚举某个点的时候考虑以这个点为最高点的所有路径里边和最大的一条路径和
对于某个点的路径有两部分，一部分是往左子树走，另一部分是往右子树走，左子树和右子树是没有任何交集（任何公共点和公共边）的，左右子树是完全独立的，以根节点分隔的左右两侧是完全独立的，让整个路径最大，让左右两边都取最大值

110 平衡二叉树
当前节点的求值依赖于左右节点，故采用后序遍历
注意：全局变量的使用，每次递归看是否修改了全局变量

class Solution {
public:
    bool ans;
    bool isBalanced(TreeNode* root) {
        ans = true;
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        int lh = dfs(root->left);
        int rh = dfs(root->right);
        if (abs(lh - rh) > 1) ans = false;
        return max(lh, rh) + 1;
    }
};

二叉树的层序遍历
用队列模拟层序遍历的逻辑（队列先进先出，符合一层一层遍历的逻辑），用栈来模拟递归的逻辑（栈先进后出符合递归的逻辑）

逻辑思路：
1、需要一个队列，用来遍历。大数组：用来存所有遍历的数据，小数组用来存当前层的数据
2、
每次遍历队列时
记录下当前队列长度（一层的数量）
当前小数组
每次都按照当前层的数量来进行遍历（处理当前层）
每次弹出一个
进行处理（推进小数组）
将其左右推进队列
将小数组中的数组推进大数组

102 二叉树的层序遍历
用队列来遍历，队列每次存的是当前这一层的数据量，然后每次按照当前层的数量来弹数据

class Solution {
public:
    queue<TreeNode*> q;
    vector<vector<int>> res;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return res;
        q.push(root);

        while (q.size())
        {
            int len = q.size();
            vector<int> path;
            while (len --)
            {
                auto t = q.front();
                q.pop();
                path.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(path);
        }

        return res;
    }
};

107 二叉树的层序遍历II

class Solution {
public:
    vector<vector<int>> res;
    queue<TreeNode*> q;

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (root) q.push(root);

        while (q.size())
        {
            vector<int> vec;
            int len = q.size();

            while (len --)
            {
                auto t = q.front();
                vec.push_back(t->val);
                q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }

            res.push_back(vec);
        }

        reverse(res.begin(), res.end()); //反转即可
        return res;
    }
};

199 二叉树的右视图
层序遍历，记录每层最右边的数即可

class Solution {
public:
    queue<TreeNode*> q;
    vector<int> res;
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return res;
        q.push(root);

        while (q.size())
        {
            int len = q.size();
            for (int i = 0; i < len; i ++)
            {
                auto t = q.front();
                q.pop();
                if  (i == len - 1)
                    res.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }

        return res;
    }
};

637 二叉树的层平均值
注意：不能用while循环，因为len --，之后长度就变了

class Solution {
    public:
    queue<TreeNode*> q;
    vector<double> res;
    
    vector<double> averageOfLevels(TreeNode* root) {
        if (root) q.push(root);
        
        while (q.size())
        {
            int len = q.size();
            double sum = 0;
            while (len --)
            {
                auto t = q.front();               
                q.pop();
                sum += t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(sum / len);
        }
        
        return res;
    }
};

class Solution {
public:
    queue<TreeNode*> q;
    vector<double> res;
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) return res;
        q.push(root);

        while (q.size())
        {
            int len = q.size();
            double sum = 0;
            for (int i = 0; i < len; i ++) // 处理当前层
            {
                auto t = q.front();
                q.pop();
                sum += t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(sum / len);
        }

        return res;
    }
};

515 在每个树行中找最大值
层序遍历，取每行的最大值

class Solution {
public:
    queue<TreeNode*> q;
    vector<int> res;
    vector<int> largestValues(TreeNode* root) {
        if (!root) return res;
        q.push(root);

        while (q.size())
        {
            int len = q.size();
            int val = INT_MIN;
            while (len --)
            {
                auto t = q.front();
                q.pop();
                val = max(val, t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(val);
        }

        return res;
    }
};

二叉搜索树

98 验证二叉搜索树
二叉搜索树按照中序遍历的话是一个递增的序列

class Solution {
public:
    TreeNode* pre = NULL;
    bool isValidBST(TreeNode* root) {
        return dfs(root);
    }

    bool dfs(TreeNode* root)
    {
        if (root == NULL) return true;
        auto left = dfs(root->left);
        if (pre && pre->val >= root->val) return false;
        pre = root;
        auto right = dfs(root->right);
        return left && right;
    }
};

108 将有序数组转换为二叉搜索树
一棵树是二叉搜索树等价于它的中序遍历是有序的。数组中间的位置作为树的根节点，然后依次的找根节点，递归处理左子树和右子树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int l, int r)
    {
        if (l > r) return NULL;
        int mid = l + r >> 1;
        auto node = new TreeNode(nums[mid]);
        node->left = build(nums, l, mid - 1);
        node->right = build(nums, mid + 1, r);
        return node;
    }
};

230 二叉搜索树中第k小的元素

class Solution {
public:
    stack<TreeNode*> stk;
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        // 用遍历的方式
        while (root || stk.size()) // 遍历树的结构
        {
            // 找到初始点
            while (root)
            {
                stk.push(root);
                root = root->left;
            }
            
            root = stk.top();
            stk.pop();
            count ++;
            if (count == k)
                return root->val;
            root = root->right;
        }

        return root->val;
    }
};

700 二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return NULL;
        if (root->val == val) return root;
        else if (root->val > val) {
            return searchBST(root->left, val);
        }
        else if (root->val < val) {
            return searchBST(root->right, val);
        }
        return root;
    }
};