程序猿养成之路：Hello树先生 - 《LeetCode刷题笔记》

树的数据结构
树的递归
- Maximum Depth of Binary Tree">LeetCode NO.104 Maximum Depth of Binary Tree
- Balanced Binary Tree">LeetCode NO.110 Balanced Binary Tree
- Diameter of Binary Tree">LeetCode NO.543 Diameter of Binary Tree
- Path Sum III">LeetCode NO.437 Path Sum III
- Symmetric Tree">LeetCode NO.101 Symmetric Tree
- Delete Nodes And Return Forest">LeetCode NO.1110 Delete Nodes And Return Forest

title: 程序猿养成之路：Hello树先生
date: 2021-03-18 12:13:14
tags:

程序猿养成之路
算法

树的数据结构

作为（单）链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有两个子节点；且除非题目说明，默认树中不存在循环结构。LeetCode 默认的树表示方法如下。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

可以看出，其与链表的主要差别就是多了一个子节点的指针。

树的递归

LeetCode NO.104 Maximum Depth of Binary Tree

题目描述

返回二叉树的最大深度。

题解

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

LeetCode NO.110 Balanced Binary Tree

题目描述

判断二叉树是否平衡。

题解

bool isBalanced(TreeNode* root) {
    return height(root)!=-1;
}
int height(TreeNode* root){
    if(root == NULL) return 0;
    int leftheight = height(root->left);
    int rightheight = height(root->right);
    if(leftheight == -1 || rightheight == -1 || abs(leftheight-rightheight) > 1) return -1;
    return 1+max(leftheight,rightheight);
}

LeetCode NO.543 Diameter of Binary Tree

题目描述

寻找二叉树的最长直径。直径的定义是二叉树上任意两节点之间的无向距离。

题解

int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    helper(root,diameter);
    return  diameter;
}
int helper(TreeNode* root , int& diameter){
    if(root == NULL ) return 0;
    int l = helper(root->left,diameter),r = helper(root->right,diameter);
    diameter = max(l+r,diameter);
    return 1+max(l,r);
}

LeetCode NO.437 Path Sum III

题目描述

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

``` 10 / \ 5 -3

/ \ \


> 3     2     11<br />
/  \       <br />
3   -2      1
> Return 3. The paths that sum to 8 are:
> 1. 5 -> 3
> 2. 5 -> 2 -> 1
> 3. -3 -> 11
**题解**
```cpp
class Solution {
public:
    /*前缀和解法
     *前缀和的概念：一个节点的前缀和就是该节点到根之间的路径和。
     *前缀和的意义：因为对于同一路径上的两个节点，上面的节点是下面节点的祖先节点，所以其前缀和之差即是这两个节点间的路径和（不包含祖先节点的值）。
     *哈希map的使用：key是前缀和， value是该前缀和的节点数量，记录数量是因为有出现复数路径的可能。
     *回溯的意义：因为只有同一条路径上的节点间（节点和其某一祖先节点间）的前缀和做差才有意义。所以当前节点处理完之后，需要从map中移除这一个前缀和，然后再进入下一个分支路径。
     */
    int pathSum(TreeNode* root, int sum) {
        //key：前缀和   value：前缀和出现的次数
        unordered_map<int,int> preFixSum;
        //初始化map
        preFixSum[0] = 1;
        int curSum = 0;
        int res = 0;
        //递归子树
        recur(root,sum,0,res,preFixSum);
        return res;
    }
    void recur(TreeNode* root,int sum,int curSum,int& res,unordered_map<int,int>& preFixSum){
        if(root==NULL) return;
        //计算当前节点前缀和
        curSum += root->val;
        //查找map，计算当前有多少前缀和为curSum-sum的节点
        res+=preFixSum[curSum-sum];
        preFixSum[curSum]++;
        //递归左右子树
        recur(root->left,sum,curSum,res,preFixSum);
        recur(root->right,sum,curSum,res,preFixSum);
        //回溯，恢复原状
        preFixSum[curSum]--;
    }
};

LeetCode NO.101 Symmetric Tree

题目描述

判断一棵二叉树是否对称。

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

程序猿养成之路：Hello树先生 - 图1

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

程序猿养成之路：Hello树先生 - 图2

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

题解

判断一个树是否对称等价于判断左右子树是否对称。笔者一般习惯将判断两个子树是否相等或对称类型的题的解法叫做“四步法”：（1）如果两个子树都为空指针，则它们相等或对称；（2）如果两个子树只有一个为空指针，则它们不相等或不对称；（3）如果两个子树根节点的值不相等，则它们不相等或不对称；（4）根据相等或对称要求，进行递归处理。

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

LeetCode NO.1110 Delete Nodes And Return Forest

题目描述

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

程序猿养成之路：Hello树先生 - 图3

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Example 2:

Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

题解

/**
 * 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) {}
 * };
 */

//后序遍历写法
TreeNode* deleteNode(TreeNode* root,set<int>& dict,vector<TreeNode*>& forest){
    if(root==NULL) return roo
    root->left = deleteNode(root->left,dict,forest);
    root->right = deleteNode(root->right,dict,forest);
     //查找节点并删除
    if(dict.find(root->val)!=dict.end()){
        if(root->left){
            forest.push_back(root->left);
        }
        if(root->right){
            forest.push_back(root->right);
        } 
        root = NULL;
    }
    return root;

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
    vector<TreeNode*> forest;
    set<int> dict(to_delete.begin(),to_delete.end()
    root = deleteNode(root,dict,forest);
    if(root){
        forest.push_back(root);
    }
    return forest;
}

/**
 * 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) {}
 * };
 */

//前序遍历写法，较为繁琐
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete){
    vector<TreeNode*> forest;
    set<int> dict(to_delete.begin(),to_delete.end());
    TreeNode* prev = NULL;
    root = deleteNode(root,dict,forest,prev);
    if(root){
        forest.push_back(root);
    }
    return fore
}

TreeNode* deleteNode(TreeNode* root,set<int>& dict,vector<TreeNode*>& forest,TreeNode* prev){
    if(root==NULL) return NULL;
    TreeNode* l = root->left;
    TreeNode* r = root->right;
    prev = root;
    if(dict.find(root->val)!=dict.end()){
        if(l && dict.find(l->val)==dict.end()){
            forest.push_back(l);
        }
        if(r && dict.find(r->val)==dict.end()){
            forest.push_back(r);
        }
        root = NULL;

    if(prev){
        prev->left = deleteNode(l,dict,forest,prev);
        prev->right = deleteNode(r,dict,forest,prev);
    }
    return root;
}