Skip to content

Latest commit

 

History

History
1064 lines (766 loc) · 26.1 KB

4.binary_tree_leetcode.md

File metadata and controls

1064 lines (766 loc) · 26.1 KB
Raw

二叉树 递归Leetcode刷题

#144 二叉树的前序遍历

太简单了，直接上代码

 void preorder(TreeNode *root, vector<int> &ans) {
        if (root == nullptr) return ;
        ans.push_back(root->val);
        preorder(root->left, ans);
        preorder(root->right, ans);
        return ;
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }

#589 N 叉树的前序遍历

思想一样，只不过用auto做一个孩子的循环

void __preorder(Node *root, vector<int> &ans) {
        if (root == nullptr) return ;
        ans.push_back(root->val);
        for (auto x : root->children) {
            __preorder(x, ans);
        }
        return ;
    }
    vector<int> preorder(Node* root) {
        vector<int> ans;
        __preorder(root, ans);
        return ans;
    }

#226 翻转二叉树

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

#剑指 Offer 32 - II. 从上到下打印二叉树 II

// 其实就是层序遍历二叉树
    void getResult(TreeNode *root, int k, vector<vector<int>> &ans) {
        // k用来标记当前root节点的值放到哪个数组
        if (root == nullptr) return ;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        getResult(root->left, k + 1, ans);
        getResult(root->right, k + 1, ans);
        return ;
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        getResult(root, 0, ans);
        return ans;
    }

模拟一下getResult

    3
   / \
  9  20
    /  \
   15   7

对于这样的一个树，k一开始为0 == ans.size()

所以向ans新增一维数组，存放3

之后向左子树递归，k = 1 == ans.size()

继续添加新的维度，存放9

之后向右子树递归，不增加新的维度

在ans[1]存放20

ans[
    0:[3]
    1:[9][20]
    2:[15][7]
]

#107 二叉树的层序遍历 II

    3
   / \
  9  20
    /  \
   15   7

ans[
    [15,7],
    [9,20],
    [3]
]

观察发现和上一题的ans就是做了对称

和上个题一样，只需复用上一题的代码。

然后对二维数组换位就行

void getResult(TreeNode *root, int k, vector<vector<int>> &ans) {
        if (root == nullptr) return ;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        getResult(root->left, k + 1, ans);
        getResult(root->right, k + 1, ans);
        return ;
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        getResult(root, 0, ans);
        for (int i = 0, j = ans.size() - 1; i < j; i++, j--) {
            // 双指针实现换位
            // 这是本题主要学到的编程技巧
            swap(ans[i], ans[j]);
        }
        return ans;
    }

#103 二叉树的锯齿形层序遍历

还是那个树

    3
   / \
  9  20
    /  \
   15   7

ans[
    [3],
    [20,9],
    [15,7]
]

只不过这回变成了一行正着来，一行倒着来

还是按照复用的框架，对ans[i]里的元素进行转换

void getResult(TreeNode *root, int k, vector<vector<int>> &ans) {
        if (root == nullptr) return ;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        getResult(root->left, k + 1, ans);
        getResult(root->right, k + 1, ans);
        return ;
    }

    void reverse(vector<int> &ans) {
        for (int i = 0, j = ans.size() - 1; i < j; i++, j--) {
            swap(ans[i], ans[j]);
        }
        return ;
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        getResult(root, 0, ans);
        for (int i = 1; i < ans.size(); i += 2) {
            reverse(ans[i]);
        }
        return ans;
    }

主要是学习n叉树的实现方法

借助队列

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    void getResult(Node *root, int k, vector<vector<int>> &ans) {
        if (root == nullptr) return ;
        if (ans.size() == k) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        for (auto x : root->children) {
            getResult(x, k + 1, ans);
        }
        return ;
    }
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        getResult(root, 0, ret);
        return ret;
    }
};

# 110 平衡二叉树

判断子树高度，首先要获取子树高度

下面是一个getHeight方法

int getHeight(TreeNode *root) {
    if (root == nullptr) return 0;
    int l = getHeight(TreeNode *root);
    int r = getHeight(TreeNode *root);
    return max(l, r) + 1;
    // 每次的 + 1就完成了对树深度的记录
}

如何将它改写成判断是否平衡呢

条件有：

  1. 左右子树高度必须 > 0
  2. 左右子树高度差 <= 1
int getHeight(TreeNode *root) {
        if (root == nullptr) return 0;
        int l = getHeight(root->left);
        int r = getHeight(root->right);
        if (l < 0 || r < 0) return -2;
        if (abs(l - r) > 1) return -2;
        // 这个函数的巧妙之处在于将原来返回int型的深度
    	// 转变成-2就是不平衡，利用负数返回值实现了判断平衡
    	// 所以说设计递归函数最重要的是设定他的意义
        return max(l, r) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return getHeight >= 0;
    }

#112 路径总和

bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr) return root->val == targetSum;
        if (root->left && hasPathSum(root->left, targetSum - root->val)) return true;
        if (root->right && hasPathSum(root->right, targetSum - root->val)) return true;
        return false;
    }

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

和手动完成是一样的步骤

  1. 找根节点位置
  2. 递归建立左子树
  3. 递归建立右子树

image-20230220190546797

重点过程就是拆成绿色黄色，也就是左右子树的前中序遍历

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return nullptr;
        int pos = 0;
        // 因为inorder的第一个是根
        // 所以要这样找inorder的根在哪个位置，用pos记录
        while (inorder[pos] != preorder[0]) ++pos;
        vector<int> l_pre, l_in, r_pre, r_in;
        // 拆成左、右子树的前、中序遍历
        for (int i = 0; i < pos; i++) {
            l_pre.push_back(preorder[i + 1]);
            l_in.push_back(inorder[i]);
        }
        for (int i = pos + 1; i < preorder.size(); i++) {
            r_pre.push_back(preorder[i]);
            r_in.push_back(inorder[i]);
        }
        TreeNode *root = new TreeNode(preorder[0], buildTree(l_pre, l_in), buildTree(r_pre, r_in));
        return root;
    }

这个代码还可以再优化

n用来记录当前数组的长度

因为pre.size() == in.size()

TreeNode* build(vector<int>& preorder, vector<int>& inorder, int n) {
        if (preorder.size() == 0) return nullptr;
        int pos = 0;
        while (inorder[pos] != preorder[0]) ++pos;
    	TreeNode *root = new TreeNode(preorder[0]);
    	root->left = build(preorder + 1, inorder, pos);
    	root->right = build(preorder + pos + 1, inorder + pos + 1, n - pos - 1);
    	return root;
}

#剑指 Offer 54 二叉搜索树的

找二叉搜索树第k大的节点

我们知道二叉搜索树特殊的性质是中序遍历序列为从小到大的有序序列

对于

	root
   /    \
 left   right

而言，如果右子树的节点数量大于k，那第k大的值肯定在右子树

如果右子树节点数量 == k - 1 那么第k大就是跟节点

如果k比右子树小，那么肯定在左子树

（因为是有序的序列，相当于倒着找k大）

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

    int kthLargest(TreeNode* root, int k) {
        int cnt_r = getCount(root->right);
        if (k <= cnt_r) return kthLargest(root->right, k);
        if (k == cnt_r + 1) return root->val;
        return kthLargest(root->left, k - cnt_r - 1);
        // 因为右子树和根加起来数量是cnt_r + 1
        // 也就是我们已经排除了这么多的元素，所以在左子树中找第
        // k - (cnt_r + 1)大的
    }

当然用中序遍历之后数组找第k大的也是可以的

 void in_order(TreeNode *root, vector<int> &ans) {
        if (root == nullptr) return ;
        in_order(root->left, ans);
        ans.push_back(root->val);
        in_order(root->right, ans);
        return ;
    }

    int kthLargest(TreeNode* root, int k) {
        vector<int> ans;
        in_order(root, ans);
        return ans[ans.size() - k];
    }

#剑指 Offer 26 树的子结构

bool isMatch(TreeNode *A, TreeNode *B) {
        if (B == nullptr) return true;
        if (A == nullptr) return false;
        if (A->val != B->val) return false;
        return isMatch(A->left, B->left) && isMatch(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (B == nullptr) return false;
        if (A == nullptr) return false;
        if (A->val == B->val && isMatch(A, B)) return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

662

image-20230221225020070

对于这样的一个树，其最大宽度是第三行的4

实际上这个题可以借助完全二叉树的技巧来实现

（节点编号 2 * i, 2 * i + 1）

所以借助队列来实现(空节点也算宽度)

每次处理一行

记录min和max，min为队列第一个元素的序号

max每次更新，记录新入队元素的序号

最后取最大值即可

image-20230221224658908

但是在运行时因为代码中有计算节点编号2 * i, 2 * i + 1

会出现溢出(当然可以通过改变数据类型解决，但是这治标不治本！)

typedef pair<TreeNode *, int> PNI;
    // 打包一种数据结构
    // 实现节点到队列序号的映射
    int widthOfBinaryTree(TreeNode* root) {
        queue<PNI> q;
        q.push(PNI(root, 0));
        while (!q.empty()) {
            int cnt = q.size();
            int l = q.front().second, r = q.front().second;
            for (int i = 0; i < cnt; i++) {
                TreeNode *n = q.front().first;
                int ind = q.front().second;
                r = ind;
                if (n->left) q.push(PNI(n->left, ind * 2));
                if (n->right) q.push(PNI(n->right, ind * 2 + 1));
                q.pop();
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }

对于这种情况来说

image-20230221231119277

明明节点4，5的宽度才是2

但是节点编号却占到了6，7

根本原因是什么，是3的编号就很大

所以在计算4，5编号的时候不妨将3节点的编号减去

那么想使3节点的编号变小就要从2节点入手

所以可得一个公式 $$ (父节点编号 - 父节点上一层节点最小的编号) \times2 $$ 所以代码的14，15行换成(ind - l) * 2

#968 监控二叉树

初步感受动态规划

f函数返回4个值

$f(root) = dp[2][2]$

第一维代表父节点是否放置摄像头

第一维代表当前节点是否放置摄像头

$dp[x][x]$存的数值表示在本节点达成监控需要放置的摄像头最小数量（注意是不包括父节点摄像头数量的）

$dp[0][0]$存的数值表示父节点和本节点都不放置摄像头需要的摄像头最小数量

对于dp数组来说

$dp[0][0]$代表最少放置摄像头的数量，父节点和本节点都不放，

但是为了能监视本节点，本节点的左右孩子肯定是要放的

所以 $$ dp[0][0] = \left{ \begin{array}{} l[0][1] + r[0][0] (左孩子放，右孩子不放) & \ l[0][0] + r[0][1] (左孩子不放，右孩子放) & \ l[0][1] + r[0][1] \ \ \ (左孩子放， 右孩子放) & \

\end{array} \right. $$ 并且这三种方案都能达到监视覆盖左右子树节点

更新这个数组，就能实现解题了

void getDP(TreeNode *root, int dp[2][2]) {
        if (root == nullptr) {
            // 当前节点为空的情况
            // dp[0][0]即为父节点和当前节点都不放
            // 都不放就都不能覆盖
            dp[0][0] = 0;
            // dp[0][1]代表父节点不放 但是当前节点为空
            // 无法放置 所以赋一个极大值
            dp[0][1] = 10000;
            dp[1][0] = 0;
            dp[1][1] = 10000;
            return ;
        }
        if (root->left == nullptr && root->right == nullptr) {
            // 如果是叶子节点
            // 什么都不放还想覆盖掉叶子节点 不可能做到的
            dp[0][0] = 10000;
            // 在本节点防止 需要一个就能覆盖本节点了
            dp[0][1] = 1;
            // 父节点放，当前节点就没必要放了
            dp[1][0] = 0;
            dp[1][1] = 1;
            return ;
        }
        // 定义本节点左右孩子的dp数组
        int l[2][2], r[2][2];
        getDP(root->left, l);
        getDP(root->right, r);
        // 左子树放、右子树不放；左不放，右放；左右都放
        dp[0][0] = min(min(l[0][1] + r[0][0], l[0][0] + r[0][1]), l[0][1] + r[0][1]);
        dp[1][0] = min(dp[0][0], l[0][0] + r[0][0]);
        // 当前节点放
        // l[1][0]代表左子树的父节点放，也就是当前节点放！
        // 所以这一种情况必定是第一维是1的组合
        dp[0][1] = min(min(l[1][0] + r[1][0], l[1][1] + r[1][1]), min(l[1][0] + r[1][1], l[1][1] + r[1][0])) + 1;
        // 子节点也是可放可不放 
        dp[1][1] = dp[0][1];
    }
    int minCameraCover(TreeNode* root) {
        int dp[2][2];
        getDP(root, dp);
        return min(dp[0][1], dp[0][0]);
    }

还可以用贪心来做

定义状态

  • 0：该节点无覆盖
  • 1：本节点有摄像头
  • 2：本节点有覆盖

对于左右孩子有四种情况

  1. 情况1：左右节点都有覆盖
  2. 左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头，右节点无覆盖
  • left == 0 && right == 1 左节点有无覆盖，右节点摄像头
  • left == 0 && right == 2 左节点无覆盖，右节点覆盖
  • left == 2 && right == 0 左节点覆盖，右节点无覆盖
  1. 左右节点至少有一个有摄像头

如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

  • left == 1 && right == 2 左节点有摄像头，右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖，右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头
  1. 头结点没有覆盖

以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，

class Solution {
public:
    // 节点状态 0 未被监控
    // 1 有摄像头
    // 2 被监控
    // 分成三种情况讨论
    int ans;
    int getResult(TreeNode *root) {
        if (root == nullptr) return 2;
        int left = getResult(root->left);
        int right = getResult(root->right);
        // left right都有覆盖 本层就不同了 因为是从下往上找的
        if (left == 2 && right == 2) return 0;
        // left right 有一个为0 就需要在本点放摄像头了
        if (left == 0 || right == 0) {
            ans++;
            return 1;
        }
        // 左右都有监控 本节点就被监控了
        if (left == 1 || right == 1) return 2;
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        ans = 0;
        // root没有被覆盖 也就是root的孙子节点是监控 这时候还要在root上放监控
        if (getResult(root) == 0) ans++;
        return ans;
    }
};

下面是之后的练习和代码随想录的题

#998 最大二叉树 II

这个题可以说是和#654 最大二叉树一点关系都没有

因为题意是在末尾插入，所以插入的节点要么是根节点要么是右子树的

是根节点就是 (val > root->val)

不是的话就右子树递归找到待插入的节点

class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (root == nullptr) {
            return new TreeNode(val);
        }
        if (root->val < val) {
            return new TreeNode(val, root, nullptr);
        }
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

#1302 层数最深叶子节点的和

这个其实就是深度优先遍历 当然了比较朴素

只需要再多记录一个信息即可，就是最大深度

当当前深度 == 最大深度的时候 就修改答案

当当前深度比最大深度还大的时候，就更新最大深度

并且初始化答案

class Solution {
public:
    // k为当前深度 max_k记录最大深度
    void getResult(TreeNode *root, int k, int &max_k, int &ans) {
        if (root == nullptr) return ;
        if (k == max_k) ans += root->val;
        if (k > max_k) {
            max_k = k;
            ans = root->val;
        }
        getResult(root->left, k + 1, max_k, ans);
        getResult(root->right, k + 1, max_k, ans);
        return ;
    }
    int deepestLeavesSum(TreeNode* root) {
        int max_k = 0, ans = 0;
        getResult(root, 1, max_k, ans);
        return ans;
    }
};

另外与此一模一样的题

#513 找树左下角的值

就是找到最深层的第一个节点就好了

class Solution {
public:
    // k为当前深度 max_k记录最大深度
    void getResult(TreeNode *root, int k, int &max_k, int &ans) {
        if (root == nullptr) return ;
        if (k > max_k) {
            max_k = k;
            ans = root->val;
        }
        getResult(root->left, k + 1, max_k, ans);
        getResult(root->right, k + 1, max_k, ans);
        return ;
    }
    int findBottomLeftValue(TreeNode* root) {
        int max_k = 0, ans = 0;
        getResult(root, 1, max_k, ans);
        return ans;
    }
};

#面试题 04.08 首个共同祖先

递归函数的返回值语义信息为：

找到了p, q或者p, q的公共祖先三种情况

如果p，q存在于当前节点的左右两侧

那么左右递归即可

class Solution {
public:
    // 一遍递归即可！
    // 定义当前函数返回值的含义
    // 找到了p, q或者p, q的公共祖先
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return root;
        if (root == p || root == q) return root;
        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);
        // l r都不为空
        // 就说明在左右子树都找了p q
        // 拿当前节点就是最近公共祖先呗！
        if (l && r) return root;
        // 否则就去左 右子树分别递归
        if (l) return l;
        return r;
    }
};

617

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

654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树

  1. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

#450 删除二叉搜索树中的节点

先找到节点

再删除节点

只不过注意删除的时候几种情况

  1. 没右子树，左子树顶上来
  2. 没左子树，右子树顶上来
  3. 比较复杂，左右子树都不为空，此时需要根节点的右子节点作为新根节点，

同时右子节点的左子树的最左边的节点，要成为根节点的左节点

WHY？因为这个左边的节点是大于左子树的最小的节点了，刚好能满足BST的性质

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
        } else {
            root->left = deleteNode(root->left, key);
        }
        if (root->val == key) {
            if (!root->right) return root->left;
            if (!root->left) return root->right;
            TreeNode *p = root->right;
            while (p->left) p = p->left;
            p->left = root->left;
            root = root->right;
        }
        return root;
    }
};

#1038 从二叉搜索树到更大和

这个题还是挺有意思的

优先要读懂题意 读懂题意这个题就做出来了

由于题目中给的是搜索二叉树，也就是中序遍历是一个有序的数组

对于 [1, 4, 6, 9]

这样的中序序列来说

求更大和二叉树就是从后往前累加！

[20, 19, 15, 9]

从后往前遍历 也就是右中左遍历

注意设置一个变量保存上一层的结果就行

class Solution {
public:
    int val = 0;
    void getResult(TreeNode *root) {
        if (root == nullptr) return ;
        getResult(root->right);
        root->val += val;
        val = root->val;
        getResult(root->left);
    }
    TreeNode* bstToGst(TreeNode* root) {
        if (root == nullptr) return root;
        val = 0;
        getResult(root);
        return root;
    }
};

77.组合

回溯法

设置一个 path 记录深度

每次更新ind的值 防止重复

class Solution {
public:
    void getResult(int n, int k, int ind, vector<int> &path, vector<vector<int>> &ret) {
        if (path.size() == k) {
            ret.push_back(path);
            return ;
        }
        for (int i = ind; i < n + 1; i++) {
            path.push_back(i);
            getResult(n, k, i + 1, path, ret);
            cout << i << endl;
            path.pop_back();
        }
        return ;
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        vector<vector<int>> ret;
        getResult(n, k, 1, path, ret);
        return ret;
    }
};

04.12

class Solution {
public:
    int getPathSum(TreeNode *root, int sum) {
        if (root == nullptr) return 0;
        return (root->val == sum) + getPathSum(root->left, sum - root->val) + getPathSum(root->right, sum - root->val);
    }
    int pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        int a = getPathSum(root, sum);
        // 选择root 就传sum - root->val
        // 不选root 就传sum
        return a + pathSum(root->left, sum) + pathSum(root->right, sum);

    }
};

491

class Solution {
public:
    void getResult(vector<int> &nums, int k, vector<int> buff, vector<vector<int>> &ret) {
        // 不为空就能push
        // 从k开始选
        // 可以选k可以不选k 就变成dp了
        if (buff.size() > 1) ret.push_back(buff);
        buff.push_back(0);
        // 哈希表去重
        unordered_map<int, int> can;
        for (int i = k; i < nums.size(); i++) {
            if (can.find(nums[i]) != can.end()) continue;
            if (buff.size() == 1 || nums[i] >= buff[buff.size() - 2]) {
                buff[buff.size() - 1] = nums[i];
                can[nums[i]] = 1;
                getResult(nums, i + 1, buff, ret);
            }
        }
        return ;
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> ret;
        getResult(nums, 0, vector<int>(), ret);
        return ret;
    }
};