链表
在之前的内容中我们学习了链表的这一基础数据结构,单链表是其中的一种,结构形式如下所示:
# Definition for the singly-linked list.
Class ListNod:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
树结构其实跟单链表差不多,只不过其指针域有多个指针域
图
区别就是图的每个节点是连着的,有入度和出度的。而树的节点不要求
树是N
(N>=0 )个节点的有限集合。N=0 时为空树,N>0 时应满足:
m
(m>0 )个互不相交的有限集合。其中,每一个有限集合自身又 是一棵树如果是无序树,上述两个树可以当作是同一颗树;如果是有序树,上述两个树不能当作是同一棵树。
定义
二叉树是一种每个节点度都不大于2的树。其中,每个节点的子节点有左右之分且左右子节点所在的子树不可以交换位置,即二叉树是一棵有序树。
上述是两颗不同的二叉树。
上述中就蓝色的树是满二叉树。
满二叉树T的高度为h,节点总数为n,则n=2^h -1 ,第k层节点总数为2^{k-1} 从1开始,对T从上到下,从左到右进行编号。如果编号i到节点有父节点,则其父节点编号为[i/2] ,如果有左节点,则其左子节点编号为2i
, 如果有右子节点,则其右子节点编号为2i+1 完全二叉树
上图中橙色以及蓝色的树是完全二叉树。
完全二叉树的叶子节点只可能存在于最下面的两层中,且最下层的叶子节点全部是靠左紧密排列的 完全二叉树中父子节点之间的编号规律与满二叉树的规律完全相同,且编号大于[n/2] 的节点 必是叶子节点 如果n为奇数,则每个非叶子节点都有两个子节点;如果n为偶数,则第n/2个节点必为非叶子 节点,且它只有左子结点而无右子节点,其余非叶子节点都有两个子节点
二叉搜索树经典的应用场景就是存放有序数据,提升查找效率。用同一个有序序列,可以构造出多个不同的二叉搜索树
左右都是二叉搜索树,但右边是特殊的样式,变成了单链表的形式,尽量避免这种结构。
平衡二叉树经典的应用场景就是与二叉搜索树结合,形成平衡二叉搜索树。在构建二叉搜索树的同时借助调整策略使每个节点的左右子树高度差都不大于1,保证二叉搜素树中每个节点的左右子树都规模相当,整个树看起来更加“匀称”。
与图的存储结构基本相似
不一样的是有一个父节点这一列,根节点的父节点设置为-1
。
与单链表类似,有children节点
上述是插入与删除的图示,与单链表基本相似。
def dfs(TreeNode root):
if not root:
return
print(root.val) # 第一次进入当前节点,访问第一次
dfs(root.left) # 优先进入左子节点
print(root.val) # 第二次进入当前节点
dfs(root.right) # 其次进入右子节点
print(root.val) # 访问第三次
return # 左右子节点全部进入过,返回到父节点
根节点第一次“进入”时,其余节点均未被“进入”;
第二次“进入”时,左子树节点全部完成三次“进先“访问”根,再“访问”左子树,最后“访问”右子树,即入”;第三次“进入”时,右子树先序遍历节点全部完成三次“进入”
# 将打印操作视为一次“访问”
# 第一次“进入”后“访问”:1, 2, 4, 5, 3, 6
def dfs(TreeNode root):
if not root:
return
print(root.val)
dfs(root.left) # 优先进入左子节点
dfs(root.right) # 其次进入右子节点
return # 左右子节点全部进入过,返回到父节点
这就是先序遍历:根 --> 左 --> 右
根节点第一次“进入”时,其余节点均未被“进入”;第二次“进入”时,左子树节点全部完成三次“进先“访问”左子树,再“访问”根,最后“访问”右子树,进入”;第三次“进入”时,右子树节点全部完成三次“进入”
# 将打印操作视为一次“访问”
# 第二次“进入”后“访问”:4, 2, 5, 1, 3, 6
def dfs(TreeNode root):
if not root:
return
dfs(root.left) # 优先进入左子节点
print(root.val)
dfs(root.right) # 其次进入右子节点
return # 左右子节点全部进入过,返回到父节点
这就是中序遍历:左 --> 根 --> 右
根节点第一次“进入”时,其余节点均未被“进入”;第二次“进入”时,左子树节点全部完成三次“进先“访问”左子树,再“访问”右子树,最后“访问”根,进入”;第三次“进入”时,右子树节点全部完成三次“进入”
# 将打印操作视为一次“访问”
# 第三次“进入”后“访问”:4, 5, 2, 6, 3, 1
def dfs(TreeNode root):
if not root:
return
dfs(root.left) # 优先进入左子节点
dfs(root.right) # 其次进入右子节点
print(root.val) # 访问第三次
return # 左右子节点全部进入过,返回到父节点
这就是后序遍历:左 --> 右 --> 根
要实现二叉树的广度有限搜索,需要借助一个特殊的数据结构——队列
实现二叉树层次遍历的流程:
def bfs(self, root: Optional[TreeNode]):
q = [] # 队列
q.append(root) # 队列初始化
while len(q) and q[0]:
cur = q.pop()
print(cur.val) # 访问
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return None
但是建议用下面的写法,添加一个每层节点个数变量,将层与层能够进行隔离:
def bfs(self, root: Optional[TreeNode]):
q = [] # 队列
q.append(root) # 队列初始化
while len(q) and q[0]:
size = len(q) # 记录当前层中节点的总数
for i in range(size): # for 循环内部负责控制同一层内节点级别操作
cur = q.pop()
print(cur.val) # 访问
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return None
树的问题一般是求树的深度,树的遍历,对称树等。一般解法是dfs,bfs递归方式。
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路
dfs一般是用递归的形式
bfs一般是用迭代循环完成
dfs
设置变量tmp记录当前节点深度 将tmp作为dfs函数参数传递到子节点 程序第一次“进入”节点后更新tmp “进入”空节点时说明完成一条路径的遍历,更新结果ans
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
self.ans = 0
tmp = 0
self.dfs(root, tmp, self.ans)
return self.ans
def dfs(self, root: TreeNode, tmp: int, ans: int):
if not root:
self.ans = max(tmp, ans)
return None
tmp = tmp + 1
self.dfs(root.left, tmp, self.ans)
self.dfs(root.right, tmp, self.ans)
return None
也可以简化为
程序遇到空节点时返回空节点的高度0给父节点 程序第三次“进入”节点时,其两个子节点的最大高度都已计算出来并返回给了该节点 根据子节点的最大高度可以计算出来当前节点的最大高度
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left_high = self.maxDepth(root.left)
right_high = self.maxDepth(root.right)
return max(left_high, right_high) + 1
bfs
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
# bfs
ans = 0
q = []
q.append(root)
while len(q) and q[0]:
ans += 1
size = len(q)
for i in range(size):
cur = q.pop(0)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return ans
dfs
/**
* 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 maxDepth(TreeNode* root) {
if(root == nullptr)
{
return 0;
}
else{
int left_high = maxDepth(root->left);
int right_high = maxDepth(root->right);
return max(left_high, right_high) + 1;
}
}
};
bfs
/**
* 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 maxDepth(TreeNode* root) {
if (root == nullptr)
{
return 0;
}
queue <TreeNode*> lst;
lst.push(root);
int ans = 0;
while(!lst.empty())
{
int sz = lst.size();
ans++;
while(sz>0)
{
TreeNode* node = lst.front();
lst.pop();
if(node->left)
{
lst.push(node->left);
}
if(node->right)
{
lst.push(node->right);
}
sz--;
}
}
return ans;
}
};
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1:
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入:nums = [1,3]
输出:[3,1]
解释:[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
nums
按 严格递增 顺序排列解题思路
二叉搜索树的中序遍历就是严格递增的顺序序列, 另外尽量平衡一些,可以将列表的中间元素作为根节点,左右两边又是顺序序列,可以递归的方式构建二叉搜索树。
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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
low = 0
high = len(nums) - 1
return self.helper(nums, low, high)
def helper(self, nums: List[int], low: int, high: int) -> TreeNode:
if low > high:
return None
mid = int(low + (high-low) / 2)
root = TreeNode(nums[mid])
root.left = self.helper(nums, low, mid-1)
root.right = self.helper(nums, mid+1, high)
return root
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:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size()-1);
}
TreeNode* helper(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 = helper(nums, left, mid-1);
root->right = helper(nums, mid+1, right);
return root;
}
};
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
解题思路:
与求二叉树的最大深度类似,可以使用dfs或者bfs,只不过是求最小的深度
dfs
# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = 10**9
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
bfs
# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
q = []
depth = 0
q.append(root)
while q and q[0]:
depth += 1
size = len(q)
for _ in range(size):
cur = q.pop(0)
if not cur.left and not cur.right: # 每一层只要有一个节点没有子节点,即为最小深度
return depth
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return 0
dfs
/**
* 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 minDepth(TreeNode* root) {
if(root==nullptr)
{
return 0;
}
if(root->left==nullptr && root->right==nullptr)
{
return 1;
}
int min_depth = INT_MAX;
if(root->left)
{
min_depth = min(minDepth(root->left), min_depth);
}
if(root->right)
{
min_depth = min(minDepth(root->right), min_depth);
}
return min_depth+1;
}
};
bfs
/**
* 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 minDepth(TreeNode* root) {
if(root == nullptr)
{
return 0;
}
if(root->left == nullptr && root->right == nullptr)
{
return 1;
}
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while(!q.empty())
{
depth++;
int size = q.size();
for(int i=0; i<size; i++)
{
TreeNode* cur = q.front();
q.pop();
if(cur->left)
{
q.push(cur->left);
}
if(cur->right)
{
q.push(cur->right);
}
if(!cur->left && !cur->right)
{
return depth;
}
}
}
return 0;
}
};
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
叶子节点 是指没有子节点的节点。 相当于该节点没有左右子节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:
输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3:
输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。
解题思路:
观察要求我们完成的函数,我们可以归纳出它的功能:询问是否存在从当前节点 root
到叶子节点的路径,满足其路径和为 sum
。
假定从根节点到当前节点的值之和为 val
,我们可以将这个大问题转化为一个小问题:是否存在从当前节点的子节点到叶子的路径,满足其路径和为 sum - val
。
不难发现这满足递归的性质, 若当前节点就是叶子节点,那么我们直接判断 sum
是否等于 val
即可(因为路径和已经确定,就是当前节点的值,我们只需要判断该路径和是否满足条件)。若当前节点不是叶子节点,我们只需要递归地询问它的子节点是否能满足条件即可。
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not(root.left or root.right): # 递归结束条件,没有子节点了,只需要判断当前值是否与目标值一致即可
return root.val == targetSum
return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)
/**
* 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:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr)
{
return false;
}
if(!(root->left || root->right)) // 没有子节点了,只需要判断当前值是否与目标值一致即可
{
return root->val == targetSum;
}
return hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right, targetSum-root->val);
}
};
也可以用bfs广度优先遍历,使用两个队列存储,一个存储节点,一个存储该节点时候的路径和。每次都pop出来,题目中是要求到叶子节点,即该节点没有左右子节点,因此只对这类节点的路径和与目标路径和进行判断
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
queue_node = [root]
queue_val = [root.val]
while queue_node:
now = queue_node.pop(0)
now_val = queue_val.pop(0)
if not now.left and not now.right: # 要求是叶子节点,没有左右子节点
if now_val == targetSum:
return True
continue
if now.left:
queue_node.append(now.left)
queue_val.append(now.left.val+now_val)
if now.right:
queue_node.append(now.right)
queue_val.append(now.right.val+now_val)
return False
/**
* 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:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr)
{
return false;
}
queue <TreeNode* > q_node;
queue <int> q_val;
q_node.push(root);
q_val.push(root->val);
while(!q_node.empty())
{
TreeNode* now_node = q_node.front();
q_node.pop();
int now_val = q_val.front();
q_val.pop();
if(now_node->left==nullptr && now_node->right==nullptr)
{
if(now_val==targetSum)
{
return true;
}
continue;
}
if(now_node->left)
{
q_node.push(now_node->left);
q_val.push(now_val+now_node->left->val);
}
if(now_node->right)
{
q_node.push(now_node->right);
q_val.push(now_val+now_node->right->val);
}
}
return false;
}
};
实现一个二叉搜索树迭代器类BSTIterator
,表示一个按中序遍历二叉搜索树(BST)的迭代器:
BSTIterator(TreeNode root)
初始化 BSTIterator
类的一个对象。BST 的根节点 root
会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。boolean hasNext()
如果向指针右侧遍历存在数字,则返回 true
;否则返回 false
。int next()
将指针向右移动,然后返回指针处的数字。注意,指针初始化为一个不存在于 BST 中的数字,所以对 next()
的首次调用将返回 BST 中的最小元素。
你可以假设 next()
调用总是有效的,也就是说,当调用 next()
时,BST 的中序遍历中至少存在一个下一个数字。
示例:
输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
解题思路:
二叉搜索树最重要的性质是:二叉搜索树的中序遍历是有序的。这个题目直接「中序遍历」,实现二叉搜索树的升序迭代器。
具体到本题,可以有两个方法:
# 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 BSTIterator:
def __init__(self, root: TreeNode):
self.queue = collections.deque()
self.inOrder(root)
def inOrder(self, root: TreeNode):
# 中序遍历
if not root:
return None
self.inOrder(root.left)
self.queue.append(root.val)
self.inOrder(root.right)
def next(self) -> int:
return self.queue.popleft()
def hasNext(self) -> bool:
return len(self.queue) > 0
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
class BSTIterator {
private:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
vector<int> arr;
int idx;
public:
BSTIterator(TreeNode* root): idx(0), arr(inorderTraversal(root)) {}
int next() {
return arr[idx++];
}
bool hasNext() {
return (idx < arr.size());
}
};