[路飛]_leetcode 112. 路徑總和、leetcode 222. 完全二叉樹的節點個數

語言: CN / TW / HK

「這是我參與11月更文挑戰的第 27 天,活動詳情檢視:2021最後一次更文挑戰

題目1

題目來源:leetcode 112. 路徑總和

給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum ,判斷該樹中是否存在 根節點到葉子節點 的路徑,這條路徑上所有節點值相加等於目標和 targetSum 。

葉子節點 是指沒有子節點的節點。

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

示例 3:

輸入:root = [1,2], targetSum = 0\ 輸出:false  

提示:

樹中節點的數目在範圍 [0, 5000] 內\ -1000 <= Node.val <= 1000\ -1000 <= targetSum <= 1000

提出問題

  • 什麼是葉子節點?
  • 如何找一條路徑上所有節點值相加等於目標和 targetSum ?

分析

  • 所謂的葉子節點就是沒有子節點的節點一般值二叉樹的最後一層的節點
  • 遞迴遍歷二叉樹,遍歷過程中targetSum = targetSum - root.val,當遍歷到葉子節點時,判斷當前節點root是否targetSum相等,相等說明找到

虛擬碼

  • 首先判斷root是否為null,為null直接返回fasle
  • 當前節點同時不存在時,返回當前節點的值與targetSum是否相等
  • 遞迴前節點的左右節點,targetSumtargetSum - root.val

程式碼實現

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ var hasPathSum = function(root, targetSum) { if(!root) return false if(!root.left && !root.right) return root.val == targetSum return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val) };

題目2

222. 完全二叉樹的節點個數

給你一棵*完全二叉樹的根節點 root ,求出該樹的節點個數。

完全二叉樹 的定義如下:在完全二叉樹中,除了最底層節點可能沒填滿外,其餘每層節點數都達到最大值,並且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第 h 層,則該層包含 1~ 2h 個節點。

示例 1:

輸入: root = [1,2,3,4,5,6]\ 輸出: 6

示例 2:

輸入: root = []\ 輸出: 0

示例 3:

輸入: root = [1]\ 輸出: 1

提示:

  • 樹中節點的數目範圍是[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • 題目資料保證輸入的樹是 完全二叉樹

提出問題

  • 什麼是完全二叉樹?
  • 如何統計節點個數 ?

分析

  • 完全二叉樹簡單來說就是除了最後一層不時滿的以為,其他都是滿的,並且最後一層不滿的節點還需要再左側
  • 遞迴遍歷二叉樹每遍歷一次就加1

虛擬碼

  • 首先判斷root是否為null,為null直接返回0
  • 遞迴前節點的左右節點,並+1

程式碼實現

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