[路飛]_leetcode 226. 翻轉二叉樹、leetcode 102. 二叉樹的層序遍歷

語言: CN / TW / HK

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

題目1

題目來源:leetcode 226. 翻轉二叉樹

翻轉一棵二叉樹。

示例:

輸入:

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

```

提出問題

  • 什麼是翻轉二叉樹?
  • 如何實現翻轉二叉樹?

分析

  • 所謂的翻轉二叉樹就是左右子節點相互互動一下
  • 遞迴遍歷二叉樹,遍歷過程中左右子節點相互互動一下

虛擬碼

  • 首先判斷root是否為null,為null直接返回null
  • 遞迴前節點的左右節點,並賦值給l、r變數
  • 使root.left = r,root.right = l
  • 返回root

程式碼實現

/** * 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 {TreeNode} */ var invertTree = function(root) { if(!root) return null let l = invertTree(root.left) let r = invertTree(root.right) root.left = r root.right = l return root };

題目2

102. 二叉樹的層序遍歷

給你一個二叉樹,請你返回其按 層序遍歷 得到的節點值。 (即逐層地,從左到右訪問所有節點)。

示例: 二叉樹:[3,9,20,null,null,15,7], ``` 3 / \ 9 20 / \ 15 7

``` 返回其層序遍歷結果:

[ [3], [9,20], [15,7] ]

提出問題

  • 二叉樹如何進行層序?

分析

  • 遞迴遍歷二叉樹每遍歷一次,並把push陣列中,沒遞迴完一層級k加1

虛擬碼

  • 定義一個arr存入層序結果
  • 定義一個getResult方法,用於往arr push當前二叉樹節點的val,此方法三個引數分別為root,k,arr
  • 首先判斷root是否為null,為null直接返回null
  • 判斷層級k是否與arr陣列的長度length 是否一樣,一樣的話就往arr變數裡arr.push(new Array())
  • 並把當前節點root的值val pusharr[k]
  • 遞迴呼叫getResult方法 傳入 前節點的左右節點,並使k+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 levelOrder = function(root) { let arr = [] getResult(root,0,arr) return arr };

var getResult = function (root,k,arr){ if(!root) return null if(k == arr.length) arr.push(new Array()) arr[k].push(root.val) getResult(root.left, k+1 ,arr) getResult(root.right, k+1 ,arr) } ```