【刷算法】二叉树中和为某一值的路径

zxhaaa 发布于2019-08-22 18:21 / 3336人阅读

摘要：题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路二叉树的大多数问题可以使用递归来解决，本题亦如此。

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

二叉树的大多数问题可以使用递归来解决，本题亦如此。

首先应该有一个数组来存储当前路径上的节点值，遇到一个节点，计算出和目标值还差多少，如果还差0且当前节点已经是叶子节点，那么该路径就是符合题意的路径，否则，继续向该节点的左右节点继续递归处理下去。

代码实现

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function FindPath(r, expectNumber)
{
    var listAll = [];
    var list = [];
    
    function find(r, target) {
        if(r === null)
            return;
        list.push(r.val);
        target -= r.val;
        
        if(target === 0 && r.left === null && r.right === null)
            listAll.push(Array.from(list));
        find(r.left, target);
        find(r.right, target);
        list.pop();
    }
    find(r, expectNumber)
    return listAll;
}

云服务器 GPU云服务器二叉树算法最优二叉树算法图二叉树 python二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95772.html

【剑指offer】让抽象问题具体化

摘要：假设压入栈的所有数字均不相等。注意这两个序列的长度是相等的思路借助一个辅助栈来存储数据。当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。若存在，左右子树，递归检测左右子树是否复合规范。 1.包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路 1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数...

Keagan 2019-08-23 15:15 评论0 收藏0
【刷算法】求二叉树深度的递归以及非递归解法

摘要：题目描述输入一棵二叉树，求该树的深度。递归解法非递归解法原来标识当前层是否遍历完毕当前弹出元素为时，说明一层以及遍历完毕了，所以最后一层的弹出时不能再往队列里面加了题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。递归解法 function TreeNode(x) { this.val = x;...

Carl 2019-08-22 18:13 评论0 收藏0
【刷算法】判断二叉搜索树的后序遍历序列的递归实现和非递归实现

摘要：题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析所谓二叉搜索...

Anshiii 2019-08-22 18:20 评论0 收藏0