前端程式員學好演算法系列(七)二叉樹和遞歸

来源:https://www.cnblogs.com/kbnet/archive/2020/07/27/13387144.html
-Advertisement-
Play Games

144. 二叉樹的前序遍歷給定一個二叉樹,返回它的 前序 遍歷。 示例: 輸入: [1,null,2,3] 1 \ 2 / 3 輸出: [1,2,3] 有兩種通用的遍歷樹的策略: 深度優先搜索(DFS) 在這個策略中,我們採用深度作為優先順序,以便從跟開始一直到達某個確定的葉子,然後再返回根到達另一個 ...


144. 二叉樹的前序遍歷
給定一個二叉樹,返回它的 前序 遍歷。

示例:

輸入: [1,null,2,3] 
1
\
2
/
3

輸出: [1,2,3]

有兩種通用的遍歷樹的策略:

深度優先搜索(DFS)

在這個策略中,我們採用深度作為優先順序,以便從跟開始一直到達某個確定的葉子,然後再返回根到達另一個分支。

深度優先搜索策略又可以根據根節點、左孩子和右孩子的相對順序被細分為前序遍歷,中序遍歷和後序遍歷。

寬度優先搜索(BFS)

我們按照高度順序一層一層的訪問整棵樹,高層次的節點將會比低層次的節點先被訪問到。

下圖中的頂點按照訪問的順序編號,按照 1-2-3-4-5 的順序來比較不同的策略。

 

解題:
1. 前序遍歷口訣,遞歸終止條件 if(root==null) return
2. 前序遍歷先列印root的值,遞歸遍歷root的左子樹, 遞歸調用root的又子樹

3. 中序遍歷 先遞歸遍歷root的左子樹,列印root的值, 遞歸調用root的又子樹

4. 後序遍歷 先遞歸遍歷root的左子樹, 在遞歸調用root的又子樹, 列印root的值

5.前中後序遍歷的不同之處在於列印root.val的時機,掌握一種,其他也很好掌握

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
     let res = []
     function pre(root){
         if(root==null){
             return
         }
         res.push(root.val)
         if(root.left){
              pre(root.left)
         }
         if(root.right){
              pre(root.right)
         }
     }
     pre(root)
     return res
};

104. 二叉樹的最大深度
給定一個二叉樹,找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例:

給定二叉樹 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最大深度 3

解題:

我們知道,二叉樹每個節點的深度與它左右子樹的深度有關,且等於其左右子樹最大深度值加上 1 。即:maxDepth(root) = max(maxDepth(root.left),maxDepth(root.right)) + 1

以 [3,4,20,null,null,15,7] 為例:

<1>我們要對根節點的最大深度求解,就要對其左右子樹的深度進行求解

<2>我們看出。以4為根節點的子樹沒有左右節點,其深度為 1 。而以 20 為根節點的子樹的深度,同樣取決於它的左右子樹深度。



<3>對於15和7的子樹,我們可以看出其深度為 2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(root==null){
        return 0
    }
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};

226. 翻轉二叉樹
翻轉一棵二叉樹。

示例:

輸入:

4
/ \
2 7
/ \ / \
1 3 6 9
輸出:

4
/ \
7 2
/ \ / \
9 6 3 1

解題:

1.js交換兩個值A,B的重要事項 先緩存A  let tmp = A  ; 把A賦值B A = B; 把B賦值為緩存的tmp

2.我們這裡也一樣 遞歸終止條件 if(!root) return null

3.root存在時交換左右節點,在遞歸調用

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return null
    if(root) {
        var left = root.left
        root.left = root.right
        root.right = left
    }
    invertTree(root.left)
    invertTree(root.right)
    return root
};

112. 路徑總和
給定一個二叉樹和一個目標和,判斷該樹中是否存在根節點到葉子節點的路徑,這條路徑上所有節點值相加等於目標和。

說明: 葉子節點是指沒有子節點的節點。

示例: 

給定如下二叉樹,以及目標和 sum = 225
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

返回 true, 因為存在目標和為 22 的根節點到葉子節點的路徑 5->4->11->2。

解題:

1.求解從 root 到葉子節點是否存在路徑和為 sum 的路徑 hasPathSum(root, sum),可以轉換成求解從 root.left 或者 root.right 到葉子節點是否存在路徑和為 sum - root.val 的路徑,即 hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val) 。

2.本題要求必須有葉子節點所有 當root只有一個元素且root.val ==sum時不是一個正確的解。
3.我們用 root.left==null && root.right==null 時判斷最正確的解。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
      if(root==null){
          return false
      }
      if(root.left==null && root.right==null){
          return sum == root.val
      }
      if(hasPathSum(root.left,sum-Number(root.val))){
          return true
      }
      if(hasPathSum(root.right,sum-Number(root.val))){
          return true
      }
      return false
};

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • HTML元素指的是從開始標簽( start tag)到結束標簽( end tag)的所有代碼 開始標簽元素內容結束標簽 <p> this is a paragraph </p> <a href="default.htm"> this is a link </a> <br/> 註釋:開始標簽被稱為開放 ...
  • 60個\參考網址https://www.w3school.com.cn/tags/index.asp 標簽描述 <!--...--> 定義註釋。 <!DOCTYPE> 定義文檔類型。 <a> 定義錨。 <abbr> 定義縮寫。 <acronym> 定義只取首字母的縮寫。 <address> 定義文檔 ...
  • HTML:超文本標記語言,是使用標記標簽來描述網頁的一種語言,也是一種規範,一種標準,它通過標記符號來標記要顯示的網頁中的各個部分; css層疊樣式表是一種用來表現HTML(標準通用標記語言的一個應用)或XML(標準通用標記語言的一個子集)等文件樣式的的電腦語言。css不僅可以靜態地修飾網頁,還可 ...
  • HTML基本結構 document是指整個文件,它下麵就是咱們的html 超文本標記語言的結構包括"頭"(head)和主體(body) 其中"頭"部提供關於網頁的信息,"主體"部分提供網頁的具體內容 #HTML基本結構-文檔聲明 為了說明文檔使用的超文本標記原因標準,所有的超文本標記語言文檔應該以“ ...
  • 一夜無眠,學習不是為了別人,自己執行力好差,對自己過高期望,以為任務目標Soeasy,結果徘徊了幾個月,還是在原地踏步,怎麼講了?學習還是要腳踏實地,專註,不要為自己找藉口!畢竟虛長幾歲,曾經的年少輕狂高傲、曲動琴聲美妙一不復返!如今的自己在為曾經的不學習,努力向著生活買單!希望下麵可以越來越好! ...
  • 回溯演算法主要應用於樹形問題,我們先從一個簡單的演算法入手 17. 電話號碼的字母組合給定一個僅包含數字 2-9 的字元串,返回所有它能表示的字母組合。 給出數字到字母的映射如下(與電話按鍵相同)。註意 1 不對應任何字母。 示例: 輸入:"23" 輸出:["ad", "ae", "af", "bd", ...
  • 一、文檔載入模式 1.事件 三要素:事件源(觸發時間的元素);事件名稱(click點擊事件);事件處理程式(事件出發後要執行的代碼函數形式) 存在問題:瀏覽器載入一個頁面的時候,是按照自上而下的順序載入的,若將script標簽寫到head內部,在代碼執行時候,頁面還沒有載入,頁面中的DOM對象也沒有 ...
  • 作者:吉玉 智能化測試 在互動中經常需要維護大量的狀態,對這些狀態進行測試驗證成本較高,尤其是當有功能變動需要回歸測試的時候。為了降低開發測試的成本,在這方面使用強化學習模擬用戶行為,在兩個方面提效: mock介面:將學習過程中的狀態作為服務介面的測試數據; 回歸測試:根據mock介面數據回溯到特定 ...
一周排行
    -Advertisement-
    Play Games
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...