代码随想录算法训练营刷题复习10：二叉树、二叉搜索树复习2

二叉树、二叉搜索树 力扣题复习

1. 110. 平衡二叉树
2. 257. 二叉树的所有路径
3. 404. 左叶子之和
4. 513. 找树左下角的值
5. 112.路径之和
6. 113.路经总和ii
7. 450. 删除二叉搜索树中的节点
8. 701. 二叉搜索树中的插入操作

110. 平衡二叉树
左右子树高度差要小于1
->递归调用（need新的函数），遇到空就返回0
->left计算左子树高度 right计算右子树高度
->遇到-1就返回-1
->最后计算高度差，大于1就返回-1
->回到isBalance,遇到-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 getHeight(TreeNode* node) {
        if(node == NULL)
            return 0;
        int left_h = getHeight(node->left);
        if(left_h == -1)
            return -1;
        int right_h = getHeight(node->right);
        if(right_h == -1)
            return -1;
        return abs(left_h-right_h) > 1 ? -1 : 1+max(left_h,right_h);
    }
    bool isBalanced(TreeNode* root) {
        return (getHeight(root)==-1)? false:true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

257. 二叉树的所有路径

记录头结点到每个叶子节点的路径，需要用到回溯
①traversal递归函数，参数root、res、path(回溯熟悉的两件套+root)
②(前提：保证传入函数的节点非空)
第一步，先把值存到path，（to_string）
第二步，终止条件：到达叶子节点，path写入res，return
第三步，判断左孩，不空，
path加入->，递归调用
回溯，path弹出 - 和>
第四步，判断右孩，不空，同第三步处理

/**
 * 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:
    void traversal(TreeNode* cur, string path, vector<string>& res) {
        path += to_string(cur->val);

        if(cur->left==NULL && cur->right==NULL) {
            res.push_back(path);
            return;
        }

        if(cur->left != NULL) {
            path += "->";
            traversal(cur->left,path,res);
            path.pop_back();
            path.pop_back();
        }
        if(cur->right != NULL) {
            path += "->";
            traversal(cur->right,path,res);
            path.pop_back();
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        vector<string> res;
        if(root==NULL)
            return res;
        traversal(root,path,res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

404. 左叶子之和

左叶子之和：
①判root空 返回0； 判root无左右孩子，返回0；
②递归调用有返回值：
left 记录左子树的左叶子之和
满足条件：node左孩不空，node左孩没有孩（为叶子节点），更新left值
right记录右子树中的左叶子之和
返回left+right一共的左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL)
            return 0;
        if(root->left==NULL && root->right==NULL)
            return 0;
        int left_value = sumOfLeftLeaves(root->left);
        if(root->left && !root->left->left && !root->left->right)
            left_value = root->left->val;
        int right_value = sumOfLeftLeaves(root->right);
        return left_value + right_value;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

513. 找树左下角的值
层序遍历，添加记录每一层的第一个元素result（如果还有下一层直接把上一层的保存的值覆盖掉就行）

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        int result = 0;
        if(root==NULL) 
            return 0;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            for(int i=0;i<size;i++) {
                TreeNode* node = que.front();
                que.pop();
                if(i==0)
                    result = node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

112.路径之和

路径之和（这轮没写出来）

class Solution {
public:
    int traversal(TreeNode* node, int temp_sum) {
        if(!node->left && !node->right && temp_sum==0)
            return true;
        else if(!node->left && !node->right)
            return false;
        if(node->left) {
            temp_sum-=node->left->val;
            if(traversal(node->left,temp_sum))
                return true;
            temp_sum+=node->left->val;
        }
        if(node->right) {
            temp_sum-=node->right->val;
            if(traversal(node->right,temp_sum))
                return true;
            temp_sum+=node->right->val;
        }
        return false;

    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==NULL)
            return false;
        return traversal(root,targetSum-root->val);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

113.路经总和ii
也是需要用到回溯，这个题和上一个题可以再复习下。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void traversal(TreeNode* root,int temp_sum) {
        if(!root->left && !root->right && temp_sum==0) {
            res.push_back(path);
            return;
        }
        else if(!root->left && !root->right)
            return;
        if(root->left) {
            temp_sum-=root->left->val;
            path.push_back(root->left->val);
            traversal(root->left,temp_sum);
            temp_sum+=root->left->val;
            path.pop_back();
        }
        if(root->right) {
            temp_sum-=root->right->val;
            path.push_back(root->right->val);
            traversal(root->right,temp_sum);
            temp_sum+=root->right->val;
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==NULL)
            return res;
        path.push_back(root->val);
        traversal(root,targetSum-root->val);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

二叉搜索树：比大小
==①无孩子节点，直接删
②有左孩
左孩替代当前node
③有右孩
右孩替代当前node
③左右孩都存在
while找到右子树的最左下的孩儿，继承node的左子树，然后将node更新为右孩。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr)
            return root;
        if(root->val==key) {
            if(root->left==nullptr && root->right==nullptr) {
                delete root;
                return nullptr;
            }
            else if(root->right==nullptr) {
                auto retnode = root->left;
                delete root;
                return retnode;
            }
            else if(root->left==nullptr) {
                auto retnode = root->right;
                delete root;
                return retnode;
            }
            else {
                TreeNode* cur = root->right;
                //这里是找到右子树的最左叶子节点
                while(cur->left!=nullptr) 
                    cur = cur->left;
                cur->left = root->left;
                TreeNode* temp = root;
                root = root->right;
                delete temp;
                return root;
            }
        }
        if(root->val < key) {
            root->right = deleteNode(root->right,key);
        }
        if(root->val > key) {
            root->left = deleteNode(root->left,key);
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

701. 二叉搜索树中的插入操作
插入一定是在叶子节点的位置，关键在于找到插入点的位置：二叉搜索树的特性 比大小

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root->val > val)
            root->left = insertIntoBST(root->left,val);
        if(root->val < val)
            root->right = insertIntoBST(root->right,val);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14