算法：树

用户3578099

发布于 2022-03-15 14:01:19

6650

发布于 2022-03-15 14:01:19

文章被收录于专栏：AI科技时讯AI科技时讯

树

树的定义与相关概念

从链表与图开始讲起

链表

在之前的内容中我们学习了链表的这一基础数据结构，单链表是其中的一种，结构形式如下所示：

# 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 时应满足：

有且仅有一个特定的称为根的节点
N>1 时，其余节点可分为m（m>0 ）个互不相交的有限集合。其中，每一个有限集合自身又是一棵树

树的相关概念

根节点：非空树处于最上层的唯一节点，其余节点都是它的子孙后代
节点的度：节点具有的孩子节点个数
叶子节点：度为0的节点
父子节点：直接相连的一对节点，处于上层的是父节点，处于下层的是子节点
兄弟节点：由同一个父节点生出的不同节点互称兄弟节点
节点层次：由根开始记为1层，其子节点为2层，孙子节点为3层……
节点深度：节点所在的层次数
树的深度/高度：树的最大层次数
节点高度：以节点为根的子树的深度/高度
有序树：以兄弟节点为根的子树交换位置得到的新树视作与原来的树不同的树
无序树：以兄弟节点为根的子树交换位置得到的新树视作与原来的树相同的树

如果是无序树，上述两个树可以当作是同一颗树；如果是有序树，上述两个树不能当作是同一棵树。

二叉树

定义

二叉树是一种每个节点度都不大于2的树。其中，每个节点的子节点有左右之分且左右子节点所在的子树不可以交换位置，即二叉树是一棵有序树。

上述是两颗不同的二叉树。

特殊的二叉树

满二叉树
- 所有叶子节点全部在最底层，且所有非叶子节点度都是2的树

上述中就蓝色的树是满二叉树。

满二叉树T的高度为h,节点总数为n，则n=2^h -1 ,第k层节点总数为2^{k-1} 从1开始，对T从上到下，从左到右进行编号。如果编号i到节点有父节点，则其父节点编号为[i/2] ，如果有左节点，则其左子节点编号为2i，如果有右子节点，则其右子节点编号为2i+1 完全二叉树 上图中橙色以及蓝色的树是完全二叉树。

记二叉树高度为h。从1开始，对二叉树从上到下，从左到右进行编号。对高度同为h的满二叉树做同样的编号处理。如果二叉树中所有节点的编号都能与满二叉树中同样位置的节点编号一致，则该二叉树是一棵完全二叉树

完全二叉树的叶子节点只可能存在于最下面的两层中，且最下层的叶子节点全部是靠左紧密排列的完全二叉树中父子节点之间的编号规律与满二叉树的规律完全相同，且编号大于[n/2］的节点必是叶子节点如果n为奇数，则每个非叶子节点都有两个子节点；如果n为偶数，则第n/2个节点必为非叶子节点，且它只有左子结点而无右子节点，其余非叶子节点都有两个子节点

二叉搜索树（BST）
- 左子树所有节点的关键字均小于根节点的关键字
- 右子树所有节点的关键字均大于根节点的关键字
- 左右子树也均为二叉搜索树
- 二叉搜索树要么是空树，要么同时满足以下条件：

二叉搜索树经典的应用场景就是存放有序数据，提升查找效率。用同一个有序序列，可以构造出多个不同的二叉搜索树

左右都是二叉搜索树，但右边是特殊的样式，变成了单链表的形式，尽量避免这种结构。

平衡二叉树（AVL）
- 如果二叉树中每个节点的左右子树高度差都不大于1，则这棵二叉树就是平衡二叉树

平衡二叉树经典的应用场景就是与二叉搜索树结合，形成平衡二叉搜索树。在构建二叉搜索树的同时借助调整策略使每个节点的左右子树高度差都不大于1，保证二叉搜素树中每个节点的左右子树都规模相当，整个树看起来更加“匀称”。

树的基本操作

树的存储结构

顺序存储结构

与图的存储结构基本相似

不一样的是有一个父节点这一列，根节点的父节点设置为-1。

链式存储结构

与单链表类似，有children节点

树的增删改查

增删

上述是插入与删除的图示，与单链表基本相似。

查找/搜索/遍历是树的核心操作
- 遍历：按照某种规则“访问”树中的每个节点，保证每个节点都会被“访问”到且每个节点只会被“访问”一次
- “访问”：程序与节点产生交互或者在节点进行某些操作
- “进入”：程序来到了某个节点，并未与该节点产生任何交互
- 不同规则下，对同一个节点的“进入”次数可能有一次也可能有多次，但对同一个节点的“访问”只会发生一次
二叉树的深度优先搜索（DFS）二叉树的深度优先搜索，在“进入”节点时有以下约定俗成的要求：
- 必须以根节点为搜索起始节点并“进入”
- 优先“进入”当前节点的左子节点，其次“进入”当前节点的右子节点
- 如果当前节点为空节点或者左右子节点都被“进入”过，则再次“进入”父节点

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           # 左右子节点全部进入过，返回到父节点

这就是后序遍历：左 --> 右 --> 根

二叉树的广度优先搜索（BFS）从根节点开始，按层次从上到下，同层次内从左到右“访问”每一个节点也叫做层次遍历每个节点只会“进入”一次

要实现二叉树的广度有限搜索，需要借助一个特殊的数据结构——队列

实现二叉树层次遍历的流程：

初始化空队，将根节点入队
当队列非空且队头元素非空时不断重复以下操作：
- 队头节点出队并设置为当前节点
- 对当前节点进行“访问”
- 如果当前节点左子节点存在则将左子节点入队
- 如果当前节点右子节点存在则将右子节点入队

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

学习视频

https://tianchi.aliyun.com/course/932/14632

树的问题一般是求树的深度，树的遍历，对称树等。一般解法是dfs，bfs递归方式。

例题

88. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

解题思路

dfs遍历：从上往下遍历，到最后一层节点时候，其深度为0，再慢慢往上走，直到根节点，高度逐步增加
bfs遍历：层序遍历，查看有多少层，即深度是多少

dfs一般是用递归的形式

bfs一般是用迭代循环完成

python实现

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

C++实现

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;
    }
};

92 将有序树组转换为二叉搜索树

给你一个整数数组 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 按 严格递增 顺序排列

解题思路

二叉搜索树的中序遍历就是严格递增的顺序序列， 另外尽量平衡一些，可以将列表的中间元素作为根节点，左右两边又是顺序序列，可以递归的方式构建二叉搜索树。

取数组中间位置的数作为根节点，同时也将数组分割成规模大致相等的两部分
根节点左侧的子数组视为左子树，右侧的子数组视为右子树
对左右子数组重复步骤1.直到子数组为空，返回空节点

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;
    }
};

95 二叉树的最小深度

给定一个二叉树，找出其最小深度。

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

说明： 叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

解题思路：

与求二叉树的最大深度类似，可以使用dfs或者bfs，只不过是求最小的深度

python实现

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

C++实现

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;
    }
};

96 路径总和

给你二叉树的根节点 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 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。

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 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)

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:
    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出来，题目中是要求到叶子节点，即该节点没有左右子节点，因此只对这类节点的路径和与目标路径和进行判断

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 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

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:
    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

解题思路：

二叉搜索树最重要的性质是：二叉搜索树的中序遍历是有序的。这个题目直接「中序遍历」，实现二叉搜索树的升序迭代器。

具体到本题，可以有两个方法：

提前保存全部节点
迭代时计算 next 节点
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 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()

c++实现

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());
    }
};

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-03-11，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树