LeetCode 二叉树专题

末蓝、 2022-10-17 01:52 154阅读 0赞

这是整理的LeetCode上的二叉树专题，按照codeTop上的频率顺序从高到低进行整理。

# DFS与非递归写法 #

二叉树深度优先遍历有三种：

*  前序：根左右
 *  中序 ：左根右
 *  后序：左右根

## 1、前序遍历 ##

### 递归 ###

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

### 迭代 ###

vector<int> preorderTraversal(TreeNode* root) {
        
    	vector<int> v;
    	stack<TreeNode*> s;
    	s.push(root);
    	while(!s.empty()){
        
    	    TreeNode* u = s.top();
    	    s.pop();   
    	    if(!u) continue; 
    	    v.push_back(u->val);
    	    s.push(u->right);
    	    s.push(u->left);
    	}
    	return v;
    }

## 二、中序遍历 ##

### 递归 ###

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

### 迭代 ###

vector<int> inorderTraversal(TreeNode* root) {
        
        vector<int> res;
        stack<TreeNode*>treeStack;
        while(root != nullptr || !treeStack.empty()){
        
       		// 插入当前节点一直到最左
            while(root != nullptr){
        
                treeStack.push(root);
                root = root->left;
            }
            root = treeStack.top();
            res.push_back(root->val);
            treeStack.pop();
            root = root->right;
        }
        return res;
    }

## 三、后序遍历 ##

### 递归 ###

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

### 迭代 ###

我们可以发现后序遍历（左右根）可由，前序遍历（根左右）左右顺序颠倒一下为（根右左），然后整个颠倒一下得（左右根）

vector<int> postorderTraversal(TreeNode* root) {
        
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
        
            TreeNode *u = stk.top();
            stk.pop();
            if(!u) continue;
            res.push_back(u->val);
            stk.push(u->left);
            stk.push(u->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }

# BFS #

二叉树的BFS基本上就是层序遍历，会这一题基本其他也就都会了。

### [102. 二叉树的层序遍历][102.] ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_20_color_FFFFFF_t_70_g_se_x_16]  
层序遍历很明显就是用队列。

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            if(root == nullptr) return {
        };
            vector<vector<int>> res;
            queue<TreeNode*> que;
            que.push(root);
            int nextCnt = 0;
            int curCnt = 1;
            vector<int> level;
            while(!que.empty())
            {
        
                TreeNode *u = que.front();
                que.pop();
                level.push_back(u->val);
                curCnt--;
                if(u->left)
                {
        
                    que.push(u->left);
                    nextCnt++;
                }
                if(u->right)
                {
        
                    que.push(u->right);
                    nextCnt++;
                }
                if(curCnt == 0)
                {
        
                    curCnt = nextCnt;
                    nextCnt = 0;
                    res.push_back(level);
                    level.clear();
                }
            }
            return res;
        }
    };

# 二叉树路径和问题 #

### [113. 路径总和 II][113. _ II] ###

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_19_color_FFFFFF_t_70_g_se_x_16]

示例 1：

> 输入：root = \[5,4,8,11,null,13,4,7,2,null,null,5,1\], targetSum = 22  
> 输出：\[\[5,4,11,2\],\[5,8,4,5\]\]

class Solution {
        
    public:
        vector<vector<int>> res;
        vector<int> path;
    
    
        void dfs(TreeNode *root, int sum){
        
            if(root == NULL){
        
                return;
            }
            sum -= root->val;
            path.push_back(root->val);
            if(root->left == NULL && root ->right == NULL && sum == 0){
        
                res.push_back(path);
            }
            dfs(root->left, sum);
            dfs(root->right, sum);
            path.pop_back();
        }
    
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
        
            dfs(root, sum);
            return res;
        }
    };

--------------------

### [437. 路径总和 III][437. _ III] ###

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_18_color_FFFFFF_t_70_g_se_x_16]  
输入：root = \[10,5,-3,3,2,null,11,3,-2,null,1\], targetSum = 8  
输出：3  
解释：和等于 8 的路径有 3 条，如图所示。

class Solution {
        
    public:
        int pathSum(TreeNode* root, int targetSum) {
        
            if(root==nullptr)
            {
        
                return 0;
            }
            return calSum(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
        }
     
        int calSum(TreeNode *root, int sum)
        {
        
            int cnt = 0;
            if(root == nullptr) 
            {
        
                return 0;
            }
            sum -= root->val;
            if(sum == 0)
            {
        
                cnt++;
            }
            return cnt + calSum(root->left, sum) + calSum(root->right, sum);
        }
    };

--------------------

### [124. 二叉树中的最大路径和][124.] ###

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。  
示例 1：  
![在这里插入图片描述][99562ee73e2543ca86187475de41d160.png]

> 输入：root = \[1,2,3\]  
> 输出：6  
> 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_13_color_FFFFFF_t_70_g_se_x_16]

> 输入：root = \[-10,9,20,null,null,15,7\]  
> 输出：42  
> 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。  
最大的路径，可能的路径情况：

> a  
> / \\  
> b c

1.  b + a + c。
2.  b + a + a 的父结点。
3.  a + c + a 的父结点。

class Solution {
        
    public:
        int maxPathSum(TreeNode* root, int &val)
        {
        
            if (root == nullptr) return 0;
            int left = maxPathSum(root->left, val);
            int right = maxPathSum(root->right, val);
            int lmr = root->val + max(0, left) + max(0, right); // 1. b + a + c。
            int ret = root->val + max(0, max(left, right)); // 2. b + a + a 的父结点  3. a + c + a 的父结点。
            val = max(val, max(lmr, ret));
            return ret;
        }
    
        int maxPathSum(TreeNode* root) 
        {
        
            int val = INT_MIN;
            maxPathSum(root, val);
            return val;
        }
    };

--------------------

# 二叉搜索树问题 #

因为二叉搜索树的特性：  
左子树小于等于根节点的值，右子树大于等于根节点的值。  
所以，如果我们对一棵二叉搜索树做中序遍历，那么我们将会得到一个有序序列，此外如果在做二叉搜索树的查找、插入、删除等操作时也要根据这一特性来做。因此有这么一些问题。

## 删除 ##

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；  
如果找到了，删除它。  
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]  
一棵二叉搜索树的中序遍历就是递增排序的序列。

我们如果要删除二叉搜索树中某一个结点，需要**递归**删除：

*  如果删除的节点为叶子结点，直接删除（return nullptr)
 *  如果被删除的节点只有一个child，使用仅有的child代替
 *  如果被删除的节点有两个child，这样就要找到要删除结点的下一个后继结点和其父节点, 将原节点值替换为 successor 的值, 并递归删除 successor。

/**
     * 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:
        TreeNode* deleteNode(TreeNode* root, int key) {
        
            if(root == nullptr) return nullptr;
            if(key < root->val){
        
                // 当前结点值大于key值，说明key在左子树
                root->left = deleteNode(root->left, key);
            }else if(key > root->val){
        
                // 当前结点值小于key值，说明key在右子树
                root->right = deleteNode(root->right, key);
            }else{
         
                // 当前结点值等于key
                if(!root->left && !root->right){
        
                    // 如果要删除的结点刚好是叶子结点
                    return nullptr;
                }
                if(!root->left && root->right){
        
                    // 如果删除的结点只有右子树，直接返回右子树
                    return root->right;
                }
                if(!root->right && root->left){
        
                    // 如果删除的结点只有左子树，直接返回左子树
                    return root->left;
                }
                if(root->left && root->right){
        
                    // 如果删除的结点左右子树都存在
    
                    //首先找到当前结点的下一个后继结点和其父节点
                    TreeNode *ancestor = root;
                    TreeNode *successor = root->right;
                    while(successor->left){
        
                        ancestor = successor;
                        successor = successor->left;
                    }
                    root->val = successor->val; // 用下一个后继结点的值替换当前要删除的结点值
                    if(ancestor->right == successor){
        
                        ancestor->right = deleteNode(successor, successor->val); // 递归删除
                    }else{
        
                        ancestor->left = deleteNode(successor, successor->val); // 递归删除
                    }
                }
            }
            return root;
        }
    };

[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20221014/7d02162941cd4f9eb76876a24b0761f1.png
[113. _ II]: https://leetcode-cn.com/problems/path-sum-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20221014/bb672048e3e141e1a3ad359f4889bf43.png
[437. _ III]: https://leetcode-cn.com/problems/path-sum-iii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20221014/d20e2368e6ca4e389e77791ff42ea330.png
[124.]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[99562ee73e2543ca86187475de41d160.png]: /images/20221014/f0fdc83a4d444688bc30eed6d0328c6f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20221014/92028be7127d4ba481b331257fe4e0dc.png
[450.]: https://leetcode-cn.com/problems/delete-node-in-a-bst/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20221014/545d7cc3b00243a9a9f71e51e0a63a89.png