1.树

1.1树的定义

树是一种非线性数据结构，在某些时候非线性结构比线性结构处理数据时要快的多。

1.2 树的应用场景

1.2.1 Linux/Unix 文件夹与文件

1.2.2 继承

下图用树结构模拟的各类之间的继承关系

1.2.3 树的抽象数据类型

1.二叉树的定义

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

2.1 完全二叉树

2.1.1 完全二叉树的特点

若一颗二叉树的深度为 h ,除了 h 层外，其他各层节点数都达到最大个数，第 h 层所有节点都连续集中在最左边。如下图所示

完全二叉树一共分为两种情况

1.满二叉树

当深度为 k 时，满二叉树的节点个数计算公式如下：

从这个公式不难算出这里根的深度是从 1 开始的

2.最后一层叶子节点没满

这个树不满的地方一定是在底部的右侧，所以在上半部分都是满二叉树

2.2 平de二叉树（AVL 树）

2.2.1什么是平衡二叉树：

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树材料参考链接

2.3二叉搜索树

2.3.1 定义

二叉搜索树又被称为二叉查找树。其特点如下：设 x 为二叉树中的一个结点，其所有的左孩子比 x 都要小，右节点比 x 都要大。中序遍历的二叉搜索树是顺序的

参考连接-知乎

2.4 LeetCode 题目中的树

LeetCode 题目中的树是如何画的，题目中的树就是层次遍历

root = [5,4,8,11,null,13,4,7,2,null,null,null,1]

2.5 树打印递归

对于递归比较迷惑的是递归在第几层以及该层栈中的应该是多少

1.添加什么代码

2.在哪里添加这些代码，应该输出什么

（1）在递归函数最开始时

• 在最开始时根据 cout 的值输出 tab 的个数

• 输出递归函数传入的参数

（2）在每一次 return 时

• 将 count 的值进行 –
• 然后输出 return 了什么

3.二叉树的遍历

3.1_144二叉树的先序遍历

3.1.1算法描述

1.递归遍历

从先序遍历来看，首先处理的是最顶层的节点，所以要将顶层节点操作放在递归函数最前面

然后在方法体总需要定义两个分别处理左右分支的递归函数，这两个递归函数最开始输入的参数都是 root

如果最后 return （啥也没有） 则说明不对这个节点做任何操作

递归技巧：当执行到最底部节点开始使用单步逻辑函数处理数据时，最底部的节点一定是会将所有的递归函数调用完再往上一层返回

2.迭代遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dJmmzjlY-1644592285392)(F:\typora_file\gif\前序遍历.gif)]

迭代遍历需要借助栈这个结构，根右左的顺序入栈。因为栈是先进后出的，要想先输出左节点必须要先将右节点入栈，将右节点压到栈底

Step1：根节点入栈

Step2：根节点出栈。根节点的右孩子入栈；根节点的左孩子入栈

Step3：栈最顶端元素出栈

Step4：栈最顶端元素的右孩子入栈，栈最顶端元素的左孩子入栈

Step3：栈最顶端元素出栈

Step4：栈最顶端元素的右孩子入栈，栈最顶端元素的左孩子入栈

Step3 和 Step4 不断重复

栈空结束循环

数据结构：栈

3.1.2 Python代码实现

1.递归遍历

(1)C++ 代码实现

class Solution {void qian(TreeNode* root,vector<int>& res){if(root==nullptr) return;res.push_back(root->val);if(root->left!=nullptr) qian(root->left,res);if(root->right!=nullptr) qian(root->right,res);}
public:vector<int> preorderTraversal(TreeNode* root) {// 递归的方法遍历vector<int>res;qian(root,res);return res;}
};

(2)Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:res = []def qian_tra(root):if root==None:return res.append(root.val)if root.left:qian_tra(root.left)if root.right:qian_tra(root.right)qian_tra(root)return res

2.迭代遍历

（1）C++ 迭代遍历

class Solution {public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();                       // 中st.pop();result.push_back(node->val);if (node->right) st.push(node->right);           // 右（空节点不入栈）if (node->left) st.push(node->left);             // 左（空节点不入栈）}return result;}
};

（2）Python 迭代遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:stack = []res = []if not root:return []stack.append(root)while stack:cur = stack.pop()if cur.right:stack.append(cur.right)if cur.left:stack.append(cur.left)res.append(cur.val)return res

易错点：

①在迭代遍历的时候要判断左右子树是否为空在当如栈中

3.2_94 二叉树的中序遍历

3.2.1算法描述

1.递归实现

先输出 DB ，就可以知道一开始处理的节点一定被一直推推向了最左下角，最先处理的是 node D。

DB 是 A 的左子树，这个时候 A 左子树的方法应该是执行完了。

然后紧接着输出的是 node F ，既然输出了 F 那么就是执行了 B 右子树的方法，即 B 执行完左子树后剩余的方法。

递归路线图：

先执行 cur 的左子树，一直向下推，推到左子树底部的节点才开始处理数据。

再对 cur 进行单独处理

然后再执行 cur 的剩余函数，也就是右子树的处理

2.迭代遍历

数据结构：栈

Step1：先将一个节点的所有左子树入栈，直到没有左子树

Step2：出栈一个节点，判断这个节点是否有右子树

Step3：该节点有右子树，如果有右子树则以该右子树为根再不断向左向下推，直到该节点为空。节点为空是出栈一个元素（类似 node4）

一直重复 Step2 和 Step3

直到栈空

数据结构：栈

中序遍历的迭代实现中，不像是先序遍历和后序遍历先将 root 保存到 stack 中，然后一个个的 pop，而是将其暂存到 cur 变量中

一开始只是对 root 的左子树不断的进栈处理，并不先将 root append 到 res 中，所以一开始不能先将 root 进栈再出栈

所以在中序遍历中的 while 循环和其他两个 while 循环不太一样

3.2.2 代码实现

1.递归实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []def tra(root):if not root:return None# 先不做任何处理，直接推到最底端tra(root.left)res.append(root.val) # 处理最底端数据# 调用最底端方法的剩余函数tra(root.right)tra(root)return res

2.迭代实现

(1) C++ 代码实现

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*>st;vector<int>res;TreeNode* cur = root;while(cur!=NULL||!st.empty()){if(cur!=NULL){ // 当前节点不为空st.push(cur); // 入栈cur = cur->left; // 如果左子树不为空则一直向上调用 while 循环}else{ // 弹栈cur = st.top();st.pop();res.push_back(cur->val);cur = cur->right;}}return res;}
};

(2) Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""stack = []res = []if not root:return rescur = root # 因为 res 最先 append 的节点不是 root ，所以不能将 root 入栈while cur or stack:if cur: # 不断的入栈左子树stack.append(cur)cur = cur.leftelse: # 已经到达了子树的最下面的最左边，这时候开始弹出 cur ，然后遍历他的右子树cur = stack.pop() # 弹出最下面最左侧元素res.append(cur.val)cur = cur.rightreturn res

3.3 _145二叉树的后序遍历

3.3.1 算法描述

1.递归算法

递归路线图：

首先输出的是 D ，也就是说函数是一直向下向左走的，直到走到头然后处理的 D

第二个输出的是 F ，中序遍历输出的是 B 。这两个不一样是在于，是先对 D 处理还是先对 F 处理：

从这里来看是先对 F 处理，也就是说在要执行 B 的剩余函数时他的剩余函数首先将要处理的节点直接推到了 B 最右端的节点

先处理的是 B 最右端节点 F

从上面可以看出单步执行函数是在最底端

2.迭代算法

前序遍历和后序遍历非常像

前序遍历：

cur pop ；cur .right先入栈；cur.left 再入栈

后序遍历：

cur pop；cur.left 先入栈；cur.right 再入栈

最后翻转 result 数组

数据结构：栈

3.3.2 C++ & Python 代码实现

1.递归算法

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:result = []def traversal(root):if not root:return []traversal(root.left)traversal(root.right)result.append(root.val)traversal(root)return result

2.迭代算法

(1)C++代码实现

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int>res;stack<TreeNode*>st;if(root==nullptr) return res;// 根节点入栈st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();res.push_back(cur->val);// 左孩子入栈if(cur->left!=nullptr) st.push(cur->left);if(cur->right!=nullptr) st.push(cur->right);}// 反转reverse(res.begin(),res.end());return res;}
};

(2)Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:result = []stack = []if not root:return resultstack.append(root)while stack:cur = stack.pop()result.append(cur.val)if cur.left:stack.append(cur.left)if cur.right:stack.append(cur.right)return result[::-1] # reverse the list

3.3.3 时空复杂度

3.3.4 Python 相关库

1.数组的切片

数组翻转和倒序读取

3.4_102二叉树的层次遍历

3.4.1算法描述

1.递归实现

除了递归用的栈，不需要额外的存储消耗

关键：每一次需要判断是否需要初始化子 []

2.迭代实现

广度遍历：层次遍历–队列
深度遍历：前中后序遍历–栈

迭代实现需要两层循环

第一层循环控制每一次 que ，当前 que 包含某一层的全部节点

第二层循环控制在当前层的 que 中每个节点孩子的入队操作

数据结构：队列

看结果存放层次遍历结果的是一个二维度 vector

如果使用队列的方法保存可以保证队列中当前保存的是某一层的全部节点

（1）遍历每一层

首先计算当前层有多少个节点。这个数就不变了，因为后面还会对队列增加节点。

（2）遍历每一个节点
将 cur node 弹出后将 cur 的左右孩子入队

3.4.2 C++ &Python 代码实现

2.迭代实现f

class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*>que; // 用于遍历的队列vector<vector<int>> res; // 存放结果if(root==nullptr) return res;que.push(root);while(!que.empty()){int size = que.size(); // 某一层的个数vector<int>tmp;for(int i =0;i<size;i++){TreeNode* cur = que.front();que.pop();tmp.push_back(cur->val);if(cur->left!=nullptr) que.push(cur->left);if(cur->right!=nullptr) que.push(cur->right);}res.push_back(tmp);}return res;}
};

1.递归实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:res = []def bfs(root,depth):if not root:returnif len(res)==depth:res.append([]) # 用于存放该层所有节点res[depth].append(root.val) # 将当前节点存放在第二维数组中bfs(root.left,depth+1) # 继续遍历下面的节点bfs(root.right,depth+1)bfs(root,0)return res

2.迭代实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:results = [] if not root:return resultsque = collections.deque()que.append(root)while que:size = len(que) # 当前 que 中的元素是上一层所有节点的孩子节点result = []for _ in range(size):cur = que.popleft()if cur.left:que.append(cur.left)if cur.right:que.append(cur.right)result.append(cur.val)results.append(result)return results

3.4.3 时空复杂度

3.4.4 层次遍历相关题目

• 102.二叉树的层序遍历

• 107.二叉树的层次遍历II

• 199.二叉树的右视图

• 637.二叉树的层平均值

• 429.N叉树的前序遍历

• 515.在每个树行中找最大值

• 116.填充每个节点的下一个右侧节点指针

• 117.填充每个节点的下一个右侧节点指针II

• 104.二叉树的最大深度

• 111.二叉树的最小深度

3.5_226翻转二叉树

3.5.1 算法描述

1.递归遍历

递归路线图：

（1）遍历顺序

在自己画图后发现先序遍历和后续遍历都可以

（2）参数和返回值

先序遍历重参数，后序遍历重返回值。先序遍历只要将 root 节点传入。后续遍历有返回值，但是因为这个返回值不是一个常数所以返回值不重要可以不用接收

（3）终止条件

终止条件就是 ①如果 cur 节点为 null 则 返回 null ②如果 cur 节点没有左孩子和右孩子直接不用交换返回 root

（4）单层循环逻辑

交换

2.迭代遍历

这个题将 root.left,root.right = root.right,root.left放在最前面和最后面都行

放在最前面就是 先翻转 node 2 和 node 7 ,放在后面就是先翻转 node1 和 node 3

因为前序（后序）遍历和层次遍历一样，都是先将根节点入栈（队），然后其左右孩子节点直接跟着入栈

3.5.2 C++ & python 代码实现

1.递归

(1) C++ 先序

class Solution {public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr) return nullptr;if(root->left == nullptr&& root->right==nullptr) return root;swap(root->left,root->right); // 虽然有返回值但是没有接收的，所以相当于没有invertTree(root->left);invertTree(root->right);return root;  }
};

(2) C++ 后续

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr) return nullptr;if(root->right==nullptr&&root->left==nullptr) return root;// 后续遍历invertTree(root->left);invertTree(root->right);swap(root->left,root->right);return root;}
};

（3）Python 代码实现

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return rootif root.left:self.invertTree(root.left)if root.right:self.invertTree(root.right)root.left,root.right = root.right,root.leftreturn root

2.迭代

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:stack = []if not root:return rootstack.append(root)while stack:cur = stack.pop()cur.left,cur.right = cur.right,cur.leftif cur.left:stack.append(cur.left)if cur.right:stack.append(cur.right)return root

3.层次迭代

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return rootque = collections.deque()que.append(root)while  que:size = len(que)for _ in range(size):cur = que.popleft()cur.left,cur.right = cur.right,cur.leftif cur.left:que.append(cur.left)if cur.right:que.append(cur.right)return root

4.层次递归

3.6_101对称二叉树

3.6.1 算法描述

1.递归算法

1.确定遍历顺序

这个题是从上向下判断。

先判断 node 2 和 node 2 是否对称，再判断 node 3 和 node 3 是否对称才有意义。所以要将递归函数放在后面

2.参数及返回值

参数

这个题一次要传入两个参数，左节点和右节点。只传入一个 root 参数是没有办法比较的，如果只传入一个参数两个 node 2 会分开判断

返回值

递归技巧：

先判断前面的节点，如果 return 函数放在最前面，则前面的节点不符合时会直接将函数的返回值返回，就不再调用底层的函数了。但返回 FALSE

3.结束循环的条件

先序遍历：在 return的时候如果为 true ，不能直接返回 true ，而是代表继续判断

4.单层递归逻辑

判断外层是否对称：左节点的左孩子和右节点的右孩子两两比较

判断内层是否对称：左节点的右孩子和右节点的左孩子两两比较

2.迭代算法

迭代算法也是一样，在判断的时候内侧之间判断，外侧之间判断

当进队和出队一定是两两进队然后再两两出队判断

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mbtmhOEi-1644592285393)(F:\typora_file\gif\翻转二叉树.gif)]

3.6.2 C++ & Python 代码实现

1.递归实现

(1) C++ 递归算法

class Solution {bool dfs(TreeNode* left,TreeNode* right){// 分为三种情况if(left==nullptr&&right!=nullptr) return false;else if(left!=nullptr&&right==nullptr) return false;else if(left==nullptr&&right==nullptr) return true;else if(left->val!=right->val) return false;bool wai = dfs(left->left,right->right);bool li = dfs(left->right,right->left);return wai&&li;}public:bool isSymmetric(TreeNode* root) {if(root==nullptr) return true;// 后续遍历return dfs(root->left,root->right);}
};

（2）python 递归实现

class Solution:def isSymmetric(self, root: TreeNode) -> bool:def compare(left,right):if not left and not right: return Trueelif not left and right: return Falseelif left and not right: return Falseif left.val != right.val: return Falseelse: return compare(left.left,right.right) and compare(left.right,right.left)if not root: return Truereturn compare(root.left,root.right)

2.迭代算法

class Solution:def isSymmetric(self, root: TreeNode) -> bool:que = collections.deque()if not root :return Trueque.append(root.left)que.append(root.right)while que:left = que.popleft()right = que.popleft()# 先判空if not left and not right: continue # 这里不能 reutrn Trueelif left and not right:return Falseelif not left and right:return Falseif left.val == right.val:que.append(left.left)que.append(right.right)que.append(left.right)que.append(right.left)else: return Falsereturn True

3.7_104树的最大深度

LeetCode题目链接

3.7.1算法描述

搞清楚三个概念：树的深度，树的高度，树的层数。在数据结构和 LeetCode 算法题对计算高度和深度的定义是不同的，通过下图就可以知道二者的区别。

其实从上图可以看到二者之间差别不是很大，只不过一个数的是边的长度，一个数的是节点的个数。

LeetCode 是数节点个数

数高度和深度的技巧就是：

深度：类似于海的深度，从上向下，数节点的个数高度：类似于楼层的高度，从下向上，数节点的个数

根节点的高度=二叉树的最大深度

最大深度：**max(左子树的最大深度，右子树的最大深度)+1 **，深度的话算的是节点所以在最后+1

递归路线图：

有两种方法可以数深度，一个是从上至下，一个从下至上，这里采用的是从下往上

递归技巧：

①从上至下

如果是从上至下计算则一般需要一个多添加的参数，确保上一层单步逻辑方法的处理结果可以传给下一层

并且确保单步执行方法要定义在递归方法之前

②从下至上

因为不需要处理上面传递过来的结果，所以一般不需要额外的参数

并且确保单步执行方法要定义在递归方法之后

3.7.2 C++ & Python 代码实现

1.递归-从上至下

class Solution:def maxDepth(self, root: TreeNode) -> int:def tra(root,depth):if root==None:return 0depth_left = tra(root.left,depth+1) # 左depth_right = tra(root.right,depth+1) # 右depth = max(depth_left,depth_right)+1 # 中return depthdepth = tra(root,0)return depth

这种方法在递归过程中栈的进出情况如下图所示

2.递归-从下至上

（1） C++ 代码实现

class Solution {public:int maxDepth(TreeNode* root) {if(root==nullptr) return 0;// 这个 0 的定义是可以放在这的，因为到后面往上返的时候就不会走到 left,right 这一步了int left = 0; int right = 0;left = maxDepth(root->left);right = maxDepth(root->right);return max(left,right)+1;}
};

（2）Python 代码实现

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0l_h = self.maxDepth(root.left) # 直接推到根节点，再一个个往上返回r_h = self.maxDepth(root.right)r_h = max(l_h,r_h)+1return r_h

2.迭代-层次遍历

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0 #记录深度queue = collections.deque()queue.append(root)while queue:size = len(queue)depth += 1 # 每次队中都保留某一层的所有节点for i in range(size):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth

###3.7.3 时空复杂度

1.深度遍历

时间复杂度：
$$O(n)$$
n 为二叉树节点的个数，每个节点在递归中只被遍历一次

空间复杂度：
$$O(height)=O(logn)$$

其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，最坏情况下，树呈现链状，因此空间复杂度等价于二叉树的高度

2 .广度遍历

时间复杂度：
$$O(n)$$
n 为二叉树节点的个数，每个节点在递归中只被遍历一次

空间复杂度：
$$O(n)$$

使用层次遍历需要使用队列，此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)

3.8_111树的最小深度

LeetCode题目链接

3.8.1 算法描述

树的最小深度：最小深度是从根节点到最近叶子节点的最短路径上的节点数量

常见错误：注意这里是叶子节点，下图中想要求 c 的最小深度，但是 c 的右侧是没有叶子节点的，所以要从c 的左侧算最小深度

下图的例子会更加明显：

所以当要向上返回某个节点的深度时需要判断这个节点左右两边是否有深度：

左子树为空，右子树不为空：最小深度=1+右子树的最小深度

左子树不为空，右子树为空：最小深度=1+左子树的最小深度

左右子树都不为空：最小深度 = min(左子树深度，右子树深度)

左右子树都为空：最小深度 = 1

可以使用递归/迭代的方法判断一个树的最小深度

3.8.2 C++ & Python 代码实现

1.递归-由下向上

（1）C++ 代码实现

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

(2) Python 代码实现

class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return  0 # 因为考虑到空树，所以对于没有深度的节点不能返回 None 要返回 0l_d = self.minDepth(root.left) # 直接从下向上判断r_d = self.minDepth(root.right)# 不能直接用 python 的min 取最小值，因为当深度是 0 时代表这一侧的深度没有意义，所以要判断if l_d==0 and r_d==0:return 1elif l_d==0 and r_d!=0:return r_d+1elif l_d!=0 and r_d ==0:return l_d+1else:return min(l_d,r_d)+1

2.迭代：层次迭代

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0que = collections.deque()que.append(root)depth = 1 # 根节点的深度while que:size = len(que)for _ in range(size):cur = que.popleft()if not cur.left and not cur.right: # 左子树为空右子树也为空说明到达最底层return depth if cur.left : que.append(cur.left)if cur.right :que.append(cur.right)depth += 1 # 这一层遍历完，继续遍历下一层return depth

3.9_222完全二叉树的节点个数

LeetCode题目链接

3.9.1 算法描述

这里的关键点是使用从上到下判断。先判断出根节点的深度，如果 “根” 节点是一个满二叉树则直接套满二叉树的公式。如果到了某一层不是满二叉树了，那么将这一层的节点个数向上 return 。return 完之后根只需要分别将左右两边的节点个数相加即可

e.g. node 1 不是满二叉树，然后再判断 node 2 是否是满二叉树，node2 是满二叉树直接套用公式。然后判断 node1 的右孩子 node3 ，node 3 不是，然后再判断 node3 的孩子谁是。最后 node1 的结果就是 node2+node3 的结果

如何判断完全二叉树的技巧：

可以发现在这里判断的方法很有意思，是从外侧判断的，由满二叉树的特点决定。如果最外侧节点高度相同则就是满二叉树

下图是本题变量进栈出栈的递归过程：

可以发现这里就是先处理根节点 node ①，判断在 node ① 处是否为满二叉树，不是，则分别判断左右子树，然后左右子树再一层一层遍历

递归技巧：（每天一个变晕技巧）

**1.return 时一定是从底层往调用它的顶层递归函数进行 return **

从上面手推递归栈就可以看出，是先算出 node ② 和 node ③ 的结果,return 后才算出 node ① 的结果。

先序遍历顶层的值是否会对后面产生影响，一定要看调用递归方法时是否传参

虽然这个题没有传参

在这个题中对 node ① 的处理是对底层有影响的

就在下面这个代码中，这里加了一个判断，如果 node ① 满足了满二叉树，那么后面底层的遍历是不是都不用进行了

if left_height==right_height: # 子树的左右子树高度相等就是满二叉树return (2<<left_height)-1

2.node ① 的处理结果没有影响到下面的递归函数

这里先对 node ①进行处理，但是 node ① 的值并没有当做参数传入后面的递归方法中，所以即使是对 node ① 进行处理，但是后面节点的值也都影响不到，所以看起来就像是先处理的后面节点

还是那个套路：递归函数调用的位置非常重要！！

看是在方法体的顶部还是底部，这会决定前面得到的结果是否会对后面产生影响

3.在递归中进行变量初始化

首先看一下变量初始化的位置，是在递归函数之前。

再看一下手推的递归函数绿色部分，**每一次进入递归函数时都会重新初始化 l_d 和 r_d 两个变量的值为 0 **

4.在看递归代码时有哪几个地方需要注意

3.9.2 C++ & Python 代码实现

1.递归-从上到下

(1)C++ 代码实现

class Solution {public:int countNodes(TreeNode* root) {if(root==nullptr) return 0;// 记录层数int left = 0;int right = 0;TreeNode* lroot = root->left;TreeNode* rroot = root->right;// 从孩子节点计算树的深度while(lroot!=nullptr){left+=1;lroot = lroot->left;}while(rroot!=nullptr){right+=1;rroot = rroot->right;}if(left==right){ // 直接套用公式return (2<<left)-1;}return countNodes(root->right)+countNodes(root->left)+1;}
};

(2) Python 代码实现

class Solution:def countNodes(self, root: TreeNode) -> int:if not root:return 0left_height = 0right_height = 0left = root.leftright = root.rightwhile left:left_height+=1left = left.leftwhile right:right_height+=1right = right.rightif left_height==right_height: # 子树的左右子树高度相等就是满二叉树return (2<<left_height)-1 # 满二叉树计算公式else:return self.countNodes(root.left)+self.countNodes(root.right)+1

易错：

最后返回的时候得到了左右子树的节点个数之后，别忘了给根节点 +1

2.求树的高度

class Solution {public:int countNodes(TreeNode* root) {int left = 0;int right = 0;if(root==nullptr) return 0;if(root->left!=nullptr){left = countNodes(root->left);}if(root->right!=nullptr){right = countNodes(root->right);}return left+right+1;}
};

3.9.3 时空复杂度

时间复杂度：O(n)

最坏情况下每个节点都要计算

空间复杂度：O(n)

即递归所用栈的深度，最坏是 O(n)平均是 O(logn)

3.9.4 知识扩展

1.位移动计算符

参考链接

这里不想深挖了，上面给出了比较详细的连接。或者如下图找规律

公式：2<<2 等于 2^(2+1) 会自动 +1

3.10_110 平衡二叉树

LeetCode题目链接

3.10.1 算法描述

1.递归：从下向上

（1）确定递归顺序

判断平衡二叉树一定是从下往上判断

（2）单层循环逻辑

判断是否是平衡二叉树需要用到高度，保证左右子树的高度绝对值不超过 1 。所以单层逻辑是求树高

（3）参数及返回值

返回值的话可以返回树的高度 int 类型这样才能供每一层计算高度。但是这里需要判断是否是平衡二叉树，所以还需要返回 bool 类型，对于这种需要返回两种的不同数据的可以使用一个 <0 的值代表 false ，使用 >0 的值代表 true 。

（4）终止条件

如果一个节点是空就不用继续判断了

3.10.2 Python 代码实现

class Solution:def isBalanced(self, root: TreeNode) -> bool:def tree_height(root)->int:if not root:return 0 # 自底向上得到左子树高度l_height = tree_height(root.left)# 自底向上得到右子树高度r_height = tree_height(root.right)# 在父节点判断if l_height==-1 or r_height==-1 or abs(l_height-r_height)>1: # 这里非常妙，使用 -1 代替 bool 判断return -1 else:return max(l_height,r_height)+1return tree_height(root)>=0

这个方法有一个非常妙的点：

有两个值需要 return 的时候如何处理

这里其实有两个值需要 return ,一个是 **子树是否是 AVL **，第二个就是底层树的高度

return 个 tuple 也不是不行。

作者在这里就比较巧妙的用 -1 代替子树不是 AVL ，用 >0 的值代替树的高度，因为树的高度也不能是负数，所以虽然都是 int 值，但是两个值也不会冲突

3.10.3 时空复杂度

时间复杂度：O(n)

自底向上的递归，每个节点都需要判断高度，所以时间复杂度是 O(n)

空间复杂度：O(n)

使用递归栈保存变量值，最坏情况是树呈一个链式，所以空间复杂度是 O(n)

3.11_257二叉树的所有路径

LeetCode题目链接

3.11.1 算法描述

回溯思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试，就像上图一样

先执行 node ① ，再执行 node ②，④。当 ④ 走不通了再返回 ② ，这时候执行 ② 的另一边

对 str 路径进行保存时使用了数组，数组传入的是值的地址，不初始化值是不变的。而且将一个变量当参数传入不断由上至下进行拼接

所以不需要返回值，一般没有返回值的递归题我比较喜欢使用树的结构体现。放在了代码的后面

从答案中不难看出来这几个分支的执行顺序，是先一直向下，再回溯，回溯到某个节点，再横向再向下执行

递归技巧：

1.参数传递

这里使用了一个 tmp 当做参数传到函数中。这个 tmp 不会一直被初始化，每次传入递归函数时都是上一次处理后的结果

2.递归中的分支：

从上图中看这个题一共分成了左右两个分支，初始时：每个分支都独立运行，参数互相不干扰，不会因为左边分支对 tmp 发生改变右边分支就跟着改变。

假设在执行完 1,2,4 这个路径之后，最后 tmp 是在 node 4 定义的 tmp = 1->2->4 ，但是随着 node 4 执行完毕， node 4 中的 tmp 临时变量就会被销毁，并且 node4 上面的节点 node 2 的 tmp 也会被销毁，node 1 执行 tra(root.right,tmp) 中的 tmp 其实是它自己的 tmp ,他自己的 tmp 是等于 ‘’ 的

所以 node 4 对 tmp 的改变并没有对 node 1 中的 tmp 产生变化

当前 node 执行当前 node 的临时变量

虽然是左右两个递归函数，并且左右两个递归函数之间互不影响，是因为左右两个递归函数在执行上是有顺序的，执行完左边的才执行右边的

3.11.2 C++ & Python 代码实现

1.C++

class Solution {
public:void bfs(TreeNode* root, vector<string>& res,string tmp){if(root==nullptr) return;// 叶子节点判断if(root->right==nullptr&&root->left==nullptr){tmp+=to_string(root->val);res.push_back(tmp);}bfs(root->left,res,tmp+to_string(root->val)+"->");bfs(root->right,res,tmp+to_string(root->val)+"->");}vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;string tmp = "";bfs(root,res,tmp);return res;}
};

2.Python

class Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:if not root:return []res = []def dfs(root,tmp):if not root:return # 如果是叶子节点，将 root.val 拼接到临时路径中    if root and not (root.left or root.right):res.append(tmp+str(root.val))return# 如果当前节点不是叶子节点，将 root.val+"->" 拼接到临时路径中    if root.left:dfs(root.left,tmp+str(root.val)+"->")# 如果当前节点不是叶子节点，将 root.val+"->" 拼接到临时路径中    if root.right:dfs(root.right,tmp+str(root.val)+"->")dfs(root,"")return res

3.11.3 知识点扩充

如何判断一个节点是叶子节点

if root and not (root.left,root.right)

3.11.4 时空复杂度

时间复杂度：O(n²)

这是一个回溯题，除了按照正常顺序遍历之外还有回溯过程

空间复杂度：O(n²)

最坏情况树呈一个链状，栈存储空间为 O(n)，每遍历一个节点拼接字符串的存储空间为 O(n)

由此可推平均情况 O((logn)²)

3.12_404左叶子之和

LeetCode 题目链接

3.12.1 算法概述

这里要得到左孩子和右孩子的和，但是 return 和传参的方法只能得到左孩子或者右孩孩子一侧的值。所以这里就要分别用两个变量接收左孩子和右孩子的值，最后 return 到主函数

并在最后将结果return 出去

如何判断是左叶子节点

易错点：

如果 cur 没有左孩子就 return 那是错的，因为 cur 没有左孩子不代表 cur->right 也没有左孩子

if node.left and not node.left.left and not node.left.right

3.12.2 C++&Python 代码实现

1.递归-后序遍历

(1)C++ 代码实现

class Solution {public:int sums = 0;void sumnode(TreeNode* root){if(root==nullptr) return ;// 倒数第二层节点if(root->left&&root->left->left==nullptr&&root->left->right==nullptr){sums+=root->left->val;}// 先序遍历if(root->left){sumOfLeftLeaves(root->left);} if(root->right){sumOfLeftLeaves(root->right);} }int sumOfLeftLeaves(TreeNode* root) {sumnode(root);return sums;}
};

(2)Python 代码实现

class Solution:def sumOfLeftLeaves(self, root: TreeNode) -> int:self.res = 0def dfs(root):if not root:return # 通过父节点判断该节点是否是叶子节点和左孩子if root.left and not root.left.left and not root.left.right:self.res += root.left.val# 先序遍历dfs(root.left)dfs(root.right)dfs(root)return self.res

3.12.3 时空复杂度

1.深度搜索

时间复杂度：
$$O(n)$$
n 为二叉树节点的个数，每个节点在递归中只被遍历一次

空间复杂度：
$$O(height)=O(logn)$$

其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，最坏情况下，树呈现链状，因此空间复杂度等价于二叉树的高度

2.广度搜索

时间复杂度：
$$O(n)$$
n 为二叉树节点的个数，每个节点在递归中只被遍历一次

空间复杂度：
$$O(n)$$

使用层次遍历需要使用队列，此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)

3.13_513找树左下角的值

LeetCode题目链接

3.13.1算法描述

这个题的题目要求是返回最底层的最左侧节点

首先想到的就是层次遍历，因为层次遍历是一种广度搜索算法，因为深度遍历无法知道是否是最底层

**1.递归实现 **

①遵循两个点：

找到最深的一层

找到最深一层的最左侧

②

如何找到最深的一层：

深度遍历无法找到最深点，除非再加一个深度的参数。层次遍历可以找到

如何找到最左侧的节点：

先序遍历该层时第一个遍历的就是最左侧的点

③对于叶子节点的处理

对于一个叶子节点首先判断该节点是不是当前最深层节点

如果当前最深层节点就：a. 替换当前最大深度 b.

2.迭代实现

迭代实现就是使用层次遍历，一层一层的找，找到最底层，然后最底层的最左侧节点就是要找的答案.对于下图这种情况 node 7 就是答案，node 4 不是答案

3.13.2 C++ & Python 代码实现

1.C++ 实现

(1) 层次遍历

class Solution {public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;int res;que.push(root);int maxval = 0;int maxheight = 0;while(!que.empty()){int size = que.size();for(int i =0;i<size;i++){TreeNode* cur = que.front();que.pop();if(i==0) res = cur->val; // 最左侧的左子树if(cur->left!=nullptr) que.push(cur->left);if(cur->right!=nullptr) que.push(cur->right);}}return res;}
};

1.递归-前序遍历

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:max_depth = 0leftnode = 0def dfs(root,cur_depth):nonlocal max_depth,leftnodeif not root.left and not root.right: # 如果是在叶子节点上就判断最大深度if cur_depth>max_depth:max_depth = cur_depthleftnode = root.valif root.left:dfs(root.left,cur_depth+1)if root.right:dfs(root.right,cur_depth+1)dfs(root,1)return leftnode

2.迭代-层次遍历

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:res = []que = collections.deque()que.append(root)while que:size = len(que)for i in range(size):cur = que.popleft()if i==1:res.append(root)if root.left:que.append(root.left)if root.right:que.append(root.right)return res[-1]

3.13.3 时空复杂度

1.深度搜索

时间复杂度：

n 为二叉树节点的个数，每个节点在递归中只被遍历一次，时间复杂度为 O(n)

空间复杂度：

递归函数需要栈空间，而栈空间取决于递归的深度，最坏情况下，树呈现链状，时间复杂度为 O(n)

平均空间复杂度就是树的高度，其中height 表示二叉树的高度 O(height) = O(log n)

2.广度搜索

时间复杂度：

O(n),n 为二叉树节点的个数，每个节点在递归中只被遍历一次

空间复杂度：

递归函数需要栈空间，而栈空间取决于递归的深度，最坏情况下，树呈现链状，时间复杂度为 O(n)

平均空间复杂度就是树的高度，其中height 表示二叉树的高度 O(height) = O(log n)

3.13.4 知识补充

1.noncal 的使用

参考链接

这个 nonlocal 很像 static 的定义，变量只会被初始化一次，后面会不断的对变量进行累加。

以下图的函数为例，如果没有对 x 使用 nonlocal 进行定义，最后输出 x 的值一定是 3 个 3 。因为每调用一次 work 方法就会定义一次 x=0，再进行累加后就是 3。

当只初始化一次后该值会从 3 累加到 9

最最最最关键的一点，nonlocal 只能在 Python3 下执行，在 Python 下执行会报错

3.14_112路径总和

LeetCode题目链接

3.14.1 算法描述

这个题非常像 257二叉树的所有路径。将每个节点都遍历然后使用字符串连接起来

求总和只不过是将链的结果进行相加，并在叶子节点判断最后的得到的总和是否满足题目要求

同样这里使用的是回溯的技巧，和上面那个题一模一样，只不过这里不是按照每一个链字符串进行拼接，而是将和进行累加。最后在将结果进行返回

递归技巧：

1.关于变量初始化问题

之前在记录二叉树深度笔记的时候记录过，在方法中每次初始化的变量，在每次重新调用递归函数时会被重新初始化

后面如果将这个变量 return 出去了，得到的答案也是本轮递归函数调用计算的答案

这两个变量在 return 的时候也是从底层往顶层返回

3.14.2 代码实现

1.C++ 代码实现

/*** 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 i =0;bool traversal(TreeNode* cur,int count){if(!cur->left&&!cur->right&&count==0) return true; // 叶子节点并且此时 count 正好为 0 if(!cur->left&&!cur->right&&count!=0) return false; // 但是值不为 count 的情况bool left = false; // 默认值是 false 竟然可以bool right = false;if(cur->left){count-=cur->left->val; // 递归处理节点left = traversal(cur->left,count);count+= cur->left->val; // 回溯，撤销处理结果}if(cur->right){count-=cur->right->val;right = traversal(cur->right,count);count+=cur->right->val;}return left||right; // 在前面都没有 return true 在后面就要 return false}bool hasPathSum(TreeNode* root, int targetSum) {if(root==nullptr) return false;return traversal(root,targetSum-root->val);}
};

2.Python 代码实现

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:sums = 0def dfs(root,sums,targetSum):if not root:return Falseif not root.left and not root.right:if sums+root.val==targetSum: # 在根节点对值进行判断return True else:return Falsehas_left,has_right = False,False # 需要将这两个值进行初始化，但是不会影响最后的结果if root.left:has_left = dfs(root.left,sums+root.val,targetSum) # 接收结果if root.right:has_right = dfs(root.right,sums+root.val,targetSum) # 接收结果return has_left or has_righthas = dfs(root,sums,targetSum)return has

3.14.3 时空复杂度

时间复杂度：O(n)

每个节点都要参与一次求和计算

空间复杂度：O(n)

最坏情况下是 O(n) 即树呈一条链状所有节点保存在栈中。平均情况下是 O(logn) 即树高

3.15_106从中序遍历与后序遍历构造二叉树

LeetCode题目链接

3.15.1 算法概述

就以题目中给出的中序和后序遍历构造二叉树

Step1：得到后序遍历的最后一个元素，根据后续遍历的最后一个元素将中序遍历分成左右子树

Step2：根据中序遍历的左右子树将后序遍历的数组分成左右子树

通过上面的切分就可以得到各节点左右子树包含哪些节点了。以及左右子树的中序和后序遍历。这样的话就可以在对左右子树使用递归的方法构建一棵树

Step3：使用同样方法将子树进行左子树和右子树

左子树：

中序遍历：[9]

后序遍历：[9]

右子树：

中序遍历：[15,20,7]

后序遍历：[15,7,20]

于是就可以一直递归下去

递归技巧：

这里是将递归函数位置放在了函数的最后，而这样放置的方法会先得到顶层的值，底层的值是由顶层的值传过去得到的。所以由此可以推断出这个树在构建的时候是从上到下构建的。

在用笔构建这个树的时候顺序就是先构建上面的树结构再构建下面的

本题关键:

1.数组切分关键

可以由后序遍历将中序遍历切分成两半，然后再由中序遍历左右子树的个数断定后续遍历左右子树个数

关键就是在于切分好中序数组后，中序遍历子树的节点个数应该和后序遍历子树的节点个数相同

2.delimited 的值

delimited 用于找到 root 节点在中序数组中的位置，如果 delimited 从 0 开始，最后会指向 root 的 index

在截取数组的时候是 左闭右开 的，所以就可以根据 index 将数组切分

2.构建二叉树关键

root.left = 递归函数，该递归函数可以返回某个节点
root.right = 递归函数，该递归函数可以返回某个节点

3.15.2 C++ & Python 代码实现

1.C++ 代码实现

class Solution {private:TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {if (postorder.size() == 0) return NULL;// 后序遍历数组最后一个元素，就是当前的中间节点int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 叶子节点if (postorder.size() == 1) return root;// 找到中序遍历的切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左闭右开区间：[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开，注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

2.Python 代码实现

class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:if not postorder:return None# 得到后续遍历最后一个节点root_val = postorder[-1] root = TreeNode(root_val)# 找到在中序遍历中的切割点separator_idx = inorder.index(root_val)# 将 inorder 数组切分成左右子树两个数组inorder_left = inorder[:separator_idx]inorder_right = inorder[separator_idx+1:] # 将根节点移除# 根据中序数组的大小得到后序数组的左右子树postorder_left = postorder[:len(inorder_left)]postorder_right = postorder[len(inorder_left):len(postorder)-1]# 递归root.left = self.buildTree(inorder_left,postorder_left)root.right = self.buildTree(inorder_right,postorder_right)return root

3.15.3 时空复杂度

1.时间复杂度

O(n²) 其中 n 是节点个数

O(n) 是因为 buildTree 方法的时间复杂度；在每次调用 buildTree 内部需要找到切割点。虽然在 buildTree 方法中没有嵌套 for 循环，是因为之一步骤被 数组.index 方法给代替了，寻找 index 过程的时间复杂度是 O(n)，最坏情况就是树是一条链的样子，数组元素是顺序的

一般情况 O(nlogn),即每次时间复杂度为 O(logn)

2.空间复杂度

O(n)

最坏情况下递归调用栈的深度为 n ,同理也是树是一个链式，数组树顺序

一般情况 O(logn),也就是树的高度

3.15.4 知识扩展

1.求得某个值在数组中的下标

a_index = nums.index(a)

2.相关题目

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

中序+前序/后序都可以唯一确定一颗二叉树，但是前序+后序不可以确定唯一一颗二叉树

3.16_654最大二叉树

LeetCode题目链接

3.16.1 算法描述

这个题的实现思路和上一个题是一模一样的,每次找到根节点也就是子数组中的最大值，这个最大值可以将数组再切分成两个子数组，分别作为左子树和右子树

Step1：找到切分点

对数组切分成左右子树，即将数组切分成左子树的数组和右子树的数组

Step2:递归

将左右子树的数组当做新的建树数组传入函数，递归建树

这个题和上个题不同之处就是在于如何切分数组而已

3.16.2 C++ & Python 代码实现

1.C++ 代码实现

class Solution {public:// 找到最大值的方法vector<int> getMax(vector<int>&nums,int start,int end){int maxVal = nums[start];int maxInx = start;for(int i = start;i<=end;i++){ // 左闭右闭if(nums[i]>maxVal){maxVal = nums[i];maxInx = i;} }return {maxInx,maxVal};}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size()==0) return nullptr;// 左子树的最大值int maxInx = 0,maxVal = 0;vector<int>maxV(2,0);maxV = getMax(nums,0,nums.size()-1);maxInx = maxV[0];maxVal = maxV[1];TreeNode* root = new TreeNode(maxVal);if(nums.size()==1) return root;// 左右子树拼接vector<int>numsLeft(nums.begin(),nums.begin()+maxInx);vector<int>numsRight(nums.begin()+maxInx+1,nums.end());root->left = constructMaximumBinaryTree(numsLeft);root->right = constructMaximumBinaryTree(numsRight);return root;}
};

2.Python 代码实现

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:if not nums:return None# 先找到当前数组的最大值点max_index = 0max_val = 0for i in range(len(nums)):if nums[i]>max_val:max_index = imax_val = nums[i]root = TreeNode(max_val)# 对数组进行切分nums_left = nums[:max_index]nums_right = nums[max_index+1:]# 递归root.left = self.constructMaximumBinaryTree(nums_left)root.right = self.constructMaximumBinaryTree(nums_right)return root

3.16.3 时空复杂度

1.时间复杂度

O(n²) 其中 n 是节点个数

O(n) 是因为 buildTree 方法的时间复杂度；在每次调用 buildTree 内部需要找到切割点。虽然在 buildTree 方法中没有嵌套 for 循环，是因为之一步骤被 数组.index 方法给代替了，寻找 index 过程的时间复杂度是 O(n)，最坏情况就是树是一条链的样子，数组元素是顺序的

一般情况 O(nlogn),即每次时间复杂度为 O(logn)

2.空间复杂度

O(n)

最坏情况下递归调用栈的深度为 n ,同理也是树是一个链式，数组树顺序

一般情况 O(logn),也就是树的高度

3.17_617合并二叉树

3.17.1 算法描述

这个题是构建二叉树

为了节省节点这里将 root2 依附在 root1 上

在依附的过程中有四种情况：

• 1，2 的 root（cur）都为空：直接返回 null , 他们的子树也不用再判断了
• 1 为空，2 不为空（红色部分）：直接将 cur2 以及它后面所有分治都赋给 cur1 ，返回 cur1 ，因为 cur1 后面没有子树了
• 1不为空，2 为空：同理上面，2 不用再向后判断，直接返回 cur1 即可
• 1，2 都不为空：将 cur2 的值累加到 cur1 上，然后继续判断，即继续进行递归

3.17.2 C++ & 代码实现

1.先序递归

（1）C++

class Solution {public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {// 将 root2 向 root1 上累加if(root1==nullptr&&root2==nullptr) return nullptr;else if(root1==nullptr&&root2!=nullptr){root1 = root2;return root1;} else if(root1!=nullptr&&root2==nullptr){return root1;} else{root1->val = root1->val+root2->val;// 递归左右子树root1->left = mergeTrees(root1->left,root2->left);root1->right = mergeTrees(root1->right,root2->right);} return root1;}
};

（2）Python

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:# 通过下面的方式判空无序再对两个节点同时判空if not root1: return root2if not root2: return root1# 直接在 root1 上进行合并，节省空间root1.val += root2.val # 中root1.left = self.mergeTrees(root1.left, root2.left) #左root1.right = self.mergeTrees(root1.right, root2.right) # 右return root1

代码简略写法：

如果要判断两个节点是否存在，则可以不用单独判断，用上面的代码就可以代替下面的代码

if not root1 and not root2:return None
if not root1 and root2:return root2
if root1 and not root2:return root1

2.层次迭代

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1:return root2if not root2:return root1# 两个树构建一个 queue 即可que = collections.deque()que.append(root1)que.append(root2)while que:size = len(que)cur1 = que.popleft()cur2 = que.popleft()# 只有两个节点都有右节点时, 再往queue里面放.这样才能正确的保证每次弹出来的两个元素都是正确的if cur1.left and cur2.left:que.append(cur1.left)que.append(cur2.left)if cur1.right and cur2.right: que.append(cur1.right)que.append(cur2.right)# 如果只有一个元素存在不用进 que ，直接合并成一个孩子if not cur1.left and cur2.left: cur1.left = cur2.leftif not cur1.right and cur2.right: cur1.right = cur2.rightcur1.val+=cur2.val return root1

3.17.3 时空复杂度

1.时间复杂度

2.空间复杂度

3.18_700二叉检索树中的搜索

3.18.1 算法概述

1.递归

这里采用从上到下递归的方式

而且如果在上半层就满足了 root.val =val 的这个值后，就不会再进行后面的递归操作了，而是直接返回给调用它的那个函数

2.迭代

使用二叉树的迭代法分为深度遍历和广度遍历，深度遍历就是 先中后序的遍历，需要借助栈实现；广度遍历就是层次遍历，需要借助队列实现

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

3.18.2 C++ & Python 代码实现

1.递归

（1）C++ 代码实现

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

（2）Python 代码实现

class Solution:def searchBST(self, root: TreeNode, val: int) -> TreeNode:if not root or root.val==val:return rootif root.val>val: # 向左搜索return self.searchBST(root.left,val)if root.val<val: # 向右搜索return self.searchBST(root.right,val)

2.迭代

class Solution:def searchBST(self, root: TreeNode, val: int) -> TreeNode:cur = root # 当前判断的节点while cur:if val < cur.val:cur = cur.leftelif val > cur.val:cur = cur.rightelse:return curreturn None # 遍历结束没有相同的节点

3.18.3 时空复杂度

1.递归

时间复杂度：

最坏时间复杂度：O(n)，树乘一个链状每个节点都要遍历

平均时间复杂度：O(logn) 树的高度

空间复杂度：

最坏空间复杂度：O(n)，树乘一个链状每个节点都要存放在栈周静

平均时间复杂度：O(logn) 树的高度，每次遍历只存放树中一部分的节点

2.迭代

最坏时间复杂度：O(n)，树乘一个链状每个节点都要遍历

平均时间复杂度：O(logn) 树的高度

空间复杂度：

这里有点不一样: 之前的空间复杂度是 O(n) 或者 O(logn) 但是这里为 1

因为平常的迭代或者递归要么使用栈，要么是层次遍历使用队列或者深度遍历使用栈，但是这里因为二叉搜索树的特性是不用将某个节点的左右子树进行保存的，所以空间复杂度是 O(1)

3.19_98验证二叉搜索树

3.19.1算法描述

二叉搜索树的特点就是中序遍历是顺序的，那么这个题就可以从中序遍历下手

这里相邻节点的处理类似于处理数组的相邻节点，有一个 pre 指针还有 root 指针

pre 指针最好是数值，不要初始化 None TreeNode

先遍历左子树，然后处理；处理过程中要不断切换 pre 和 root ；最后就是处理右子树

3.19.2 代码实现

1.中序递归

（1）C++

class Solution {public:long long  maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root==nullptr) return true;bool left = isValidBST(root->left); if(maxVal<root->val) maxVal = root->val;else return false;bool right = isValidBST(root->right);return left&&right;}
};

（2）Python

class Solution:def isValidBST(self, root: TreeNode) -> bool:# 中序遍历数组从小到大pre = -float('INF')def tra(root)->bool:nonlocal preif not root:return Trueres_left = tra(root.left) # 判断左子树if pre<root.val: # 二叉搜索树中不能包含相同节点pre = root.valelse:return Falseres_right = tra(root.right)return res_left and res_rightis_BST = tra(root)return is_BST

易错点：

二叉搜索树中不能包含相同的节点，当节点值相同时返回的是 False

3.20_530二叉搜索树的最小绝对差

3.20.1 算法描述

搜索二叉树的中序遍历是一个顺序数组。只要按照中序的遍历方式依次遍历相邻两个元素的差值，找到差值的最小值

[A,B,C,D] 假设这是中序遍历结果

比较 B-A ，C-B ，D-C 这几个插空之间的差值大小。因为递增，C-A 一定是大于 B-A 的，所以只考虑插空

3.20.2 C++ & Python 代码实现

1.中序递归-外部定义变量

（1）C++ 代码实现

class Solution {public:int result = INT_MAX;TreeNode* pre;void traversal(TreeNode* cur){if(cur==nullptr) return;traversal(cur->left); // 左if(pre!=nullptr) result = min(result,cur->val-pre->val);pre = cur; // 记录下一个traversal(cur->right); // 右}int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

（2）Python 代码实现

class Solution:def getMinimumDifference(self, root: TreeNode) -> int:min_val = float('INF')pre = -1 # pre 不用定义一个节点直接是一个值即可def dfs(root):nonlocal min_val,pre # 这个值是一直不变的所以要在这里使用 nonlocal 定义if not root:return float('INF')dfs(root.left)if pre!=-1:min_val = min(min_val,(root.val-pre))# 更新 prepre = root.valdfs(root.right)dfs(root)return min_val

递归技巧：

1.nonlocal 的使用

在 222 完全二叉树节点个数一题中有画栈来说明每一次调用递归函数时递归函数中声明的变量都会重新初始化一遍。

所以如果变量 min_val 和 pre 是在 dfs 方法中进行定义的，则每次调用这个方法,都会将这个变量重新初始化

但是这里题目要求是这个变量一直递归下去，但是不声明又会报错，所以在每次声明的时候添加 nonlocal 让每次递归保持变量大小不变

在 231 找树左下角的值同样适用了 nonlocal 进行递归

2.中序递归特点

当递归函数放在单步递归之前时会先将节点一直推到最后再处理节点。那么中序遍历的单步递归函数是夹在两个递归函数中间的

也就是说递归函数先一直推，一直推到中间层的元素，先处理中间层的元素。当中间层的元素处理完后在处理后面的元素

3.21_501二叉搜索树中的众数

LeetCode题目链接

3.21.1 算法描述

二叉搜索树因为中序遍历是顺序的，所以如果按照中序遍历方法遍历二叉树则就是按照数组的顺序处理二叉树节点

难点：

顺序数组求一个众数非常简单，数组中有多个众数时要记录：

①每个数出现的频次

②哪些数是众数

③前一个节点的值

这个题如同 530二叉检索树的最小绝对差相同，都需要相邻两个 node 进行比较，所以需要定义 pre 变量

对于出现频次的处理：

①如果当前数值出现的频次 > 最大频次：让当前元素直接取代 res 中的所有值

②如果当前数值出现的频次==最大频次：将该数值拼接在 res 后即可

所以总体分为两步：

S1：先对 cur 的 val 进行计数操作，相应的 curCount 应该赋值为几

curCount ++：只有当 pre 和 cur 相等时才会 ++

curCount = 1: 没有 pre || pre ! = cur

S2：根据 count 对 res 进行操作。根据上面刚刚判断完的 count 将相应的元素进行 push 或者 pop

clear()+push()：

push()：

3.21.2 代码实现

1.C++ 代码实现

class Solution {int maxCount = INT_MIN;int curCount = 0;TreeNode* pre;vector<int> res;void find(TreeNode* root){// 结束条件if(root==nullptr) return;find(root->left);// 单步循环// 对 cout 进行增加if(pre&&pre->val==root->val) curCount++;else curCount = 1;// 对 maxCount 进行判断if(maxCount==curCount) res.push_back(root->val);else if(maxCount<curCount){res.clear();res.push_back(root->val);maxCount = curCount;}pre = root;find(root->right);}public:vector<int> findMode(TreeNode* root) {find(root);return res;}
};

2.Python 代码实现

def findMode(self, root: TreeNode) -> List[int]:pre = root.valcount = 0  # 统计频率countMax = 0  # 最大频率res = []def findNumber(root):nonlocal pre,count,countMax,res # 这些变量不会被重新初始化if not root: return None   findNumber(root.left)  if pre == root.val: count += 1else:  pre = root.val # 如果后面的 root 和 pre 的值相等，则 pre 可以一直固定count = 1 # 这里的 count 是从 1 开始的不是从 0 if count > countMax:  countMax = count  res = [root.val]  # 直接将原先的 res 覆盖elif count == countMax:  res.append(root.val) # append 在 res 上findNumber(root.right)  returnfindNumber(root)return res

3.12.3 时空复杂度

时间复杂度：O(n)

每个节点都需要进行频率计算，所以是 O(n)

空间复杂度：O(n)

栈时空的空间，最坏情况下树呈一个链状，每个节点都要入栈

3.22_236二叉树的最近公共祖先

LeetCode题目链接

3.22.1算法描述

首先，所有节点的公共祖先都是根节点。本题要求最近的公共祖先

这里使用的是回溯方法

一共分为两种情况：

①p,q 为对方的祖先，就像第二张图一样

所以这里使用由上至下的方法进行判断，遇到的第一个 p 或者第一个 q 就是祖先，则不用再进行判断直接往上返

用先序遍历或者中序遍历都可以

②p,q 是一个节点的左右孩子

情况 ① 和 情况 ② 是不重叠的，是情况①就不能是情况②，所以在判断完所有节点不为 ①情况后判断是否为情况②

情况② 的成立条件是左右两棵子树都没有向上返

3.22.2 代码实现

1.C++ 代码实现

class Solution {public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);if(root==p||root==q) return root;TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left==nullptr) return right;if(right==nullptr) return left;return root;    }
};

2.python 代码实现

class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if not root:returnleft = self.lowestCommonAncestor(root.left,p,q) # 先遍历左子树if root==p or root==q: # 等于其中一个就不用再继续向后判断了return rootright = self.lowestCommonAncestor(root.right,p,q) # 再遍历右子树if not left:return rightif not right:return leftreturn root # 左右两边都有值时则返回 root 

3.Java 代码实现

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return root;if(root==p) return root;if(root==q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q); // 判断左子树是否有 p,qTreeNode right = lowestCommonAncestor(root.right,p,q); // 判断右子树是否有 p,qif(left==null) return right;if(right==null) return left;return root; // 左右子树都不为空，则 root 就是祖先}
}

3.22.4 时空复杂度

时间复杂度：O(n)

最坏情况下需要遍历二叉树所有节点

空间复杂度：O(n)

树呈链状，所有节点都存入栈中

3.23_235二叉搜索树的最近公共祖先

3.23.1 算法描述

关键：“root” 在 [p,q] 中则说明 root 是 p,q 的公共祖先，而且对于每一个点都适用

以上图这棵树为例，比如说 p,q 是 3,5 ，则其公共祖先是 4 ，并且发现其他的所有祖先节点都不符合要求

所以只需要从上到下遍历所有节点，如果 root.val 在 [p,q] 闭区间范围内则就将 root 返回，随便一种遍历方法都可

判断条件：

如果 val 在 [p,q] 范围之外，当然 p,q 不知道谁大谁小，则继续遍历下一个 ’‘root’‘

如果在范围内则跳出遍历的循环

3.23.2 代码实现

1.C++ 代码实现

class Solution {public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr) return root;// 中序遍历，如果 root 加在 q,p 中间则 root 就是公共节点，在范围之外就继续寻找if(root->val>q->val&&root->val>p->val)   lowestCommonAncestor(root->left,p,q);if(root->val<q->val&&root->val<p->val)   lowestCommonAncestor(root->right,p,q);return root;}
};

2.Python 代码实现

class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if root.val>p.val and root.val>q.val: # [] 右侧范围return self.lowestCommonAncestor(root.left,p,q)elif root.val<p.val and root.val<q.val: # [] 左侧范围return self.lowestCommonAncestor(root.right,p,q)else:return root

易错点：

①不知道 p,q 谁大谁小

不用判断p,q 谁大谁小，直接像上面一样判断范围即可

②在左右子树的时候没有 return ，但是也没有给递归的 low 方法进行赋值，导致最后返回结果没有函数接收

3.23.3 JAVA 代码实现

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(true){ // 遍历所有节点if(root.val>p.val && root.val>q.val) root=root.left; // 范围之外继续寻找else if(root.val<p.val&&root.val<q.val) root=root.right;else break; // 退出寻找   }return root;}
}

3.23.4 时空复杂度

时间复杂度：O(n)

空间复杂度：O(n)

3.24_701二叉搜索树中的插入操作

3.24.1 算法描述

这个题相当于构建树的操作，最后返回的是树的根节点。重构树操作在 106,617 中都有构建过关键步骤在于

root.left 等于哪个节点
root.right 等于哪个节点
return 需要连接的节点

一个节点有很多中插入方式，有的插入方式需要重新调整树的左右子树结构。最简单的插入方式就是在当前节点满足父类节点的情况下一遇到空节点就插入，因为这样不会调整树的结构

所以如果位置是正确的，并且当前位置的节点是空，则插入

为什么说遇到空的就可以插入：

一个节点的某个孩子为空，则代表这个节点左孩子下面什么都没有，那么也就没有所谓了其节点的左孩子不满足插入节点的情况

3.23.2 Python 代码实现

class Solution:def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:if root is None:return TreeNode(val)if val<root.val:root.left = self.insertIntoBST(root.left,val) # 左子树if val>root.val:root.right = self.insertIntoBST(root.right,val) # 右子树return root

3.24.3 Java 代码实现

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。return new TreeNode(val);if (root.val < val){root.right = insertIntoBST(root.right, val); // 递归创建右子树}else if (root.val > val){root.left = insertIntoBST(root.left, val); // 递归创建左子树}return root;}
}

3.24.4 时空复杂度

时间复杂度：O(n)

最坏时间复杂度就是树是一个链状，每个节点都要判断一遍。平均情况就是 O(logn) 只需要判断一侧的树即可

时间复杂度：O(n)

最坏空间复杂度就是树是一个链状，每个节点都要判断一遍。平均情况就是 O(logn) 只需要判断一侧的树即可

3.25_450删除二叉搜索树中的节点

Python:LeetCode题目链接

JAVA:LeetCode题目链接

3.25.1 算法描述

虽然是删除，这个题也是类似于构建二叉树，需要返回 root 节点的左右节点连接哪个节点

假设要删除 node 3 ，有个节点会替换上去，替换上的节点只需要满足它和它兄弟节点的关系，就如node 2 和 node 4

有以下几种情况：

1.没有找到删除节点，直接遍历到最后

当要删除某个节点时：

2.左右孩子都为空，则直接返回 null 让 上一层进行拼接

3.删除节点左孩子为空，右孩子不为空：返回右孩子

4.删除节点左孩子不为空，右孩子为空：返回左孩子

5.删除节点左右孩子都不为空（只采取固定一种的删除方式）： cur 节点的右孩子顶替 cur ，cur 的左孩子放到 cur 右孩子的最左

前面几个条件很容易理解，最后一个条件如下图：

如何找到 cur 节点的最下册最左侧的空节点：

结束条件是 cur.left 是空，则可以将 root.left 放上

while cur.left:cur = cur.left
此时的 cur.left 就是 cur 的最下册最左侧的空节点    

root.val < val 删除的节点比 root 大，所以这时候再遍历右侧的树

root.val > val 删除的节点比 root 小，所以这时候再遍历左侧的树

3.25.2 代码实现

1.搜索二叉树的删除

（1）C++ 代码实现

class Solution {public:TreeNode* deleteNode(TreeNode* root, int key) {if(root==nullptr) return root;// 删除操作if(root->val == key){// 1.左右孩子都为空if(root->left==nullptr&&root->right==nullptr){delete root;return nullptr;} // 2. 其中一个为空if(root->left==nullptr&&root->right!=nullptr){auto retNode = root->right;delete root;return retNode;} if(root->left!=nullptr&&root->right==nullptr){auto retNode = root->left;delete root;return retNode;} if(root->left!=nullptr&&root->right!=nullptr){// 3.两个都不为空TreeNode* cur = root->right;while(cur->left!=nullptr){cur = cur->left;}cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;return root;}}if(root->val > key) root->left = deleteNode(root->left,key);if(root->val < key) root->right = deleteNode(root->right,key);return root;}
};

易错点：

这里在判断时如果用 else if 的话就要如下面这么写

else if (root->left == nullptr) {auto retNode = root->right;///! 内存释放delete root;return retNode;
}
// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
else if (root->right == nullptr) {auto retNode = root->left;///! 内存释放delete root;return retNode;
}

在不能穷举除所有情况时还是用 if else 语句比较清楚，不要用 else if 语句

（2）Python 代码实现

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if not root:return rootif root.val==key: # 分成 5 种情况if not root.left and not root.right:del rootreturn Noneif not root.left and root.right:  tmp = rootroot = root.rightdel tmpreturn rootif root.left and not root.right:  tmp = rootroot = root.leftdel tmpreturn rootelse:v = root.rightwhile v.left:v = v.leftv.left = root.left # 将删除节点的左孩子放到他右孩子的最左端tmp = root # 保存删除节点root = root.right # 右孩子处理完成将右孩子放在删除节点上del tmpreturn rootif root.val > key: root.left = self.deleteNode(root.left,key)  #左递归if root.val < key: root.right = self.deleteNode(root.right,key)  #右递归return root

易错点：

①这里每个判断语句可以都添加上 return 但是不能都将 return 删除

2.普通二叉树的删除

普通二叉树的删除只需要将该节点额子树放到该节点位置并且删除该节点即可，会更加容易些

（3）JAVA 代码实现

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root==null){return root;}if(key>root.val){ // 继续向右寻找root.right = deleteNode(root.right,key);}else if(key<root.val){root.left = deleteNode(root.left,key);}else{if(root.left==null)return root.right;else if(root.right==null)return root.left;else{// 找到右孩子的最左节点TreeNode tmp = root.right;while(tmp.left!=null){tmp = tmp.left;}// 右孩子的最左节点接root的左孩子tmp.left = root.left;root = root.right;}}return root;}
}

3.25.3 时空复杂度

时间复杂度：O(n)

空间复杂度：O(n)

3.26_669修剪二叉搜索树

3.26.1 算法描述

假设想要删除不在范围 [1,3] 的节点，也就是 0 节点。首先 node 0 的所有左孩子一定是不满足要求的全部删除，但是 node 0 的右孩子可能会有在范围之内的。所以要继续使用递归的方法判断 cur 节点的右子树哪些需要删除

同理如果 node 0 是在右边，那么就要删除他的所有右孩子

如果 cur 满足，则继续判断它的左右子树，继续向下遍历

3.26.2 代码实现

1.C++ 代码实现

class Solution {public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return nullptr;if(root->val<low){TreeNode* right = trimBST(root->right,low,high); // 判断该节点的后续节点return right;}if(root->val>high){TreeNode* left = trimBST(root->left,low,high);return left;}// 正常判断其他节点root->left = trimBST(root->left,low,high);root->right = trimBST(root->right,low,high);return root;}
};

2.Python 代码实现

class Solution(object):def trimBST(self, root, low, high):""":type root: TreeNode:type low: int:type high: int:rtype: TreeNode"""if not root:return if root.val < low:return self.trimBST(root.right,low,high) # 继续找符合条件的节点，符合条件的节点都在 root 的右侧if root.val>high:return self.trimBST(root.left,low,high)# 构建树root.left = self.trimBST(root.left,low,high)root.right = self.trimBST(root.right,low,high)return root

3.JAVA 代码实现

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) return root;// 判断子树// cur root 在左侧，返回右孩子if(root.val<low) return trimBST(root.right,low,high); // 将 root.right 返回上去之后会继续判断 root.right 为根的结果// cur root 在右侧，返回左孩子if(root.val>high) return trimBST(root.left,low,high);// 构件树：root 在 [low,high] 范围之内，继续向下执行root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}

3.26.3 时空复杂度

时间复杂度：O(n)

最坏时间复杂度为 O(n)，树呈一个链状，每个节点都要判断

空间复杂度：O(n)

最坏空间复杂度为 O(n)，树呈一个链状，每个节点都放入栈中

3.27_108将有序数组转换为二叉搜索树

LeetCode题目链接

3.27.1 算法描述

首先，这个数组是一个有序数组，这又是一个构建树的问题。

如果想要构建平衡树：

每次选数组最中间的元素，然后将数组一分为二，下一次就选子数组中间的元素

如果想要构建搜索树：

因为数组是顺序的，所以使用上面的方法构建出来的就是搜索树,而且还能保证平衡

如果数组或者子数组是偶数怎么办

选择哪个节点为中间节点都可，因为选取哪一个都不会影响想到二叉搜索树的平衡性

3.27.2 代码实现

1.C++ 代码实现

class Solution {public:TreeNode* base(vector<int>&nums,int left,int right){if(left>right)return nullptr;int mid = left+((right-left)/2); // 找到中间点TreeNode* root = new TreeNode(nums[mid]);root->left = base(nums,left,mid-1);root->right = base(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = base(nums,0,nums.size()-1);return root;}
};

2.Python 代码实现

class Solution(object):def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""if not nums:return None# 找到中间值作为根节点media= len(nums)/2root = TreeNode(nums[media])nums_left = nums[:media]nums_right = nums[media+1:]root.left = self.sortedArrayToBST(nums_left)root.right = self.sortedArrayToBST(nums_right)return root

3.JAVA 代码实现

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length);}public TreeNode sortedArrayToBST(int[] nums,int left,int right){if(left>=right) return null;// 没有子数组可以再遍历int mid = left+(right-left)/2; // 这里不直接写 （left+right）/2 的原因是防止 (left+right) 值太大溢出上限TreeNode root = new TreeNode(nums[mid]); // 根节点root.left = sortedArrayToBST(nums,left,mid); // 根节点左子如何拼接root.right = sortedArrayToBST(nums,mid+1,right); // 根节点右子树如何拼接return root; // 返回根节点}
}

3.27.3 时空复杂度

时间复杂度：O(n)

每一个节点都需要遍历拼接，所以时间复杂度为 O(n)

空间复杂度: O(n)

最坏情况树呈一个链状，最坏空间复杂度是 O(n)

3.28_538把二叉搜索树转换为累加树

3.28.1 算法描述

根据题目中的事例，转换成中序遍历之后，可以进行如下累加：

[0,1,2,3,4,5,6,7,8] 是从后往前累加

8 还是 8

7-> 8+7=15

6->15+7

。。。。

这个题先处理的是二叉搜索树最右侧的节点也就是 8 ，然后再处理 7 ，在处理 6 。。。 这个题就是中序遍历的逆序，但是这个中序遍历先处理的节点是 right 节点，所以就要将中序遍历中先处理的 left 节点改成先处理 right 节点

因为先处理 8 再处理 7 所以还需要一个全局变量用来记录刚刚处理过的数据

3.28.2 代码实现

1.C++ 代码实现

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

2.Python 代码实现

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:sums = 0def tra_rev(root):nonlocal sumsif not root:return Nonetra_rev(root.right) # 递归右子树sums+= root.valroot.val = sumstra_rev(root.left) # 递归左子树return roottra_rev(root)return root

3.28.3 JAVA 代码实现

class Solution {int sums;public TreeNode convertBST(TreeNode root) {sums=0;convertBST1(root);return root;}public void convertBST1(TreeNode root) {if(root==null) return;// 先遍历右子树，相当于遍历数组中 pre 的值convertBST1(root.right);// 改变根节点的值sums+=root.val;root.val = sums;// 改变左子树的值convertBST1(root.left);}
}

3.28.3 时空复杂度

时间复杂度：O(n)

每个节点都要更新值进行累加

空间复杂度：O(n)

最坏时间复杂度，树呈一条链状，每次遍历将所有节点入栈

3.29_100相同的树（易错算法）

3.29.1 算法描述

这里有一个易错点，在从上到下执行时，如果某个节点是满足条件的，下一步需要做的是继续向下执行，而不是直接 返回 True

在这里体现的是

if p.val == q.val :

这一句话之后执行的是下一步的递归，而不是直接返回 True ,如果是直接返回 True ,那么就不会再调用后面的 node 了

3.29.2 代码实现

1.C++ 代码实现

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

2.Python 代码实现

class Solution(object):def isSameTree(self, p, q):""":type p: TreeNode:type q: TreeNode:rtype: bool"""if not p and not q:return Trueelif not p and q :return Falseelif p and not q :return Falseelif p.val!=q.val:return Falseelif p.val==q.val: # 这里需要注意的是，当左边和右边值相同的时候做的是继续判断，而不是直接返回 True# 向下判断左右子树l_same = self.isSameTree(p.left,q.left)r_same = self.isSameTree(p.right,q.right)return l_same and r_same

4.Top 100 题

4.1_208 实现 Trie (前缀树)

视频讲解

题目讲解

4.1.1 算法描述

它其实是一个字典树，每个节点对应的是一个字典，并不是一个单词占一个树根

4.1.2 代码实现

class Trie {private:bool isEnd; // 该字母是否是单词的最后一个字母Trie* next[26]; // 每个字母都映射一个字典,字典中存放 Trie nodepublic:Trie() { // 类似于一个节点的定义isEnd = false;memset(next,0,sizeof(next)); // 映射的字典}void insert(string word) { // 插入一个单词Trie* node = this;for(char c:word){if(node->next[c-'a']==NULL){node->next[c-'a'] = new Trie();}node = node->next[c-'a']; // 向下都一个 node }node->isEnd = true; // 最后一个 node 放置结束符}bool search(string word) { // 查找整个单词Trie* node = this;for(char c:word){node = node->next[c-'a']; // 不断向下查找下一个元素if(node==NULL) return false; // 一旦发现空就返回 false }return node->isEnd;}bool startsWith(string prefix) { // 查找前缀Trie* node = this;for(char c:prefix){node = node->next[c-'a'];if(node==NULL) return false; // 只要是空就返回 false }return true; // 最后一个字符可以不是结尾}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/