已知一颗完全二叉树共有867个结点,则该树的深度为,树的度为2时,该树为二叉树

　　二叉树中有一定值的BM29路径(1)

　　知识点树

　　给定一个二叉树根和一个值和，判断从根节点到叶节点是否有一条路径，其节点值和等于和。

　　1.这个问题的路径被定义为从树的根节点向下到叶节点的节点。2.叶节点是指没有子节点的节点。3.路径只能从父节点到子节点，不能从子节点到父节点。4.节点总数是n。

　　例如：

　　给定以下二叉树，

　　因为带有路径的节点的值之和是22。

　　数据范围：1。树上的节点数满足2。每个节点的值满足2。

　　要求：空间复杂度，时间复杂度高级：空间复杂度，时间复杂度

　　示例1输入：

　　{5，4，8，1，11，#，9，#，2，7}，22复制返回值：

　　准确的副本

　　2示例输入：

　　{1，2}，0复制返回值：

　　假拷贝

　　3示例输入：

　　{1，2}，3复制返回值：

　　准确的副本

　　示例4输入：

　　{}，0复制返回值：

　　错误的

　　递归求解问题递归求解的思想非常简单，如下：

　　1.如果当前节点也是节点，判断当前节点的和与val是否相等，如果相等，则路径存在；否则，它不存在；2.如果是非叶节点，以sum-node- val为新的和，然后递归判断左右路径是否有关注度：

　　对于空树，根据测试用例，它应该返回false，即使和为0。如果是节点，要判断是否等于sum # include bits/stdc . h。

　　定义树结构

　　{

　　int val

　　struct TreeNode * left

　　struct TreeNode * right

　　TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}

　　};

　　bool hasPathSum(TreeNode *root，int sum)

　　{

　　if (root==nullptr)

　　{

　　//return sum==0；

　　返回false

　　}

　　if(root-left==nullptr root-right==nullptr)

　　{

　　返回root-val==sum；

　　}

　　返回hasPathSum(root- left，sum-root-val) hasPathSum(root-right，sum-root-val)；

　　}非递归解法非递归解法需要借鉴层次遍历。与以前的层次遍历不同，这次我们使用一个结构来存储当前节点和通过其父节点的所有节点的总和。逻辑非常简单，代码如下：

　　#包含位/标准数据。h

　　结构路径_总和

　　{

　　int sum { 0 }；

　　TreeNode * node { null ptr }；

　　path _ sum()=default；

　　path_sum(int s，TreeNode *n) : sum(s)，node(n) {}

　　};

　　bool hashPathSum _ level(TreeNode * root，int sum)

　　{

　　if (root==nullptr)

　　{

　　返回false

　　}

　　std:队列路径_总和q；

　　STD:vector path _ sum v；

　　q.push(path_sum(0，root))；

　　而(！q.empty())

　　{

　　自动节点=q . front()；

　　//如果是叶节点，判断当前节点的值和其父节点的值之和是否等于我们的目标值。

　　if(node . node-left==nullptr node . node-right==nullptr(node . node-val node . sum==sum))

　　{

　　返回true

　　}

　　q . pop()；

　　if (node.node- left！=nullptr)

　　{

　　q . push(path _ sum(node . sum node . node-val，node . node-left))；//将左侧节点及其父节点的总和放入队列中

　　}

　　if (node.node-右！=nullptr)

　　{

　　q . push(path _ sum(node . sum node . node-val，node . node-right))；//

　　}

　　}

　　返回false

　　}

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。