前端程式員學好演算法系列（七）二叉樹和遞回

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 = 22，

5
/ \
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
};

標籤：JavaScript

上一篇：[Go] Go語言實戰-基于websocket瀏覽器通知的實作

下一篇：JavaScript連載27-檔案加載模式以及元素獲取