【刷算法】二叉樹中和為某一值的路徑

zxhaaa 發布于2019-08-22 18:21 / 3337人閱讀

摘要：題目描述輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路二叉樹的大多數問題可以使用遞歸來解決，本題亦如此。

題目描述

輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

思路

二叉樹的大多數問題可以使用遞歸來解決，本題亦如此。

首先應該有一個數組來存儲當前路徑上的節點值，遇到一個節點，計算出和目標值還差多少，如果還差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二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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