講透學爛二叉樹(六)：二叉樹的筆試題:翻轉|寬度|深度

翻轉|鏡像二叉樹

華為面試題——将二叉樹的兩個孩子換位置，即左變右，右變左。

90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

遞歸實作

先序周遊每個結點，翻轉每個結點。

下面來分析具體的實作思路：

• 對于根結點為空的情況

  這種情況需要排除，因為null不是一個對象，不可能存在左右子樹并且可以翻轉的情況

• 對根不為空的情況，翻轉該節點

JavaScript代碼實作二叉樹翻轉

reverseTree (root = this.tree) {
    if (root &&root.data) {
        [root.leftChild, root.rightChild] = [root.rightChild, root.leftChild]
        this.reverseTree(root.leftChild)
        this.reverseTree(root.rightChild)
    }
}      

循環，棧存儲（DFS，非遞歸)

本質思想是，左右節點進行交換，循環翻轉每個節點的左右子節點，将未翻轉的子節點存入棧中，循環直到棧裡所有節點都循環交換完為止。

reverseTree3 (node) {
    if (!node) {
        return 0
    }
    let queue = [node]
    while (queue.length) {
        let temp = queue.shift();
        [temp.leftChild, temp.rightChild] = [temp.rightChild, temp.leftChild]
        temp.leftChild && queue.push(temp.leftChild)
        temp.rightChild && queue.push(temp.rightChild)
    }
    return node
}      

層序周遊，翻轉每層的結點

JavaScript代碼實作

reverseTree2 (node = this.tree) {
    let buckets = [[node]]
    let i = 0

    function getChildNode (root, i) {
        if (!root || !root.data) {
            return false
        }
        i++
        if (buckets[i] === undefined) {
            buckets[i] = []
        }
        if (root.leftChild) {
            buckets[i].push(root.leftChild)
            getChildNode(root.leftChild, i)
        }
        if (root.rightChild) {
            buckets[i].push(root.rightChild)
            getChildNode(root.rightChild, i)
        }
    }
    getChildNode(node, i)
    for (let i = 0; i < buckets.length; i++) {
        for(let j=0;j<buckets[i].length;j++){
            if(i>1){
                let parentIndex = buckets[i-1].length-1-Math.floor(i/2)
                buckets[i][j]['parent']=buckets[i-1][parentIndex]
            }
            buckets[i+1].reverse()
            let leftChildIndex = i*2
            let rightChildIndex = i*2+1
            if(buckets[i+1][leftChildIndex]){
                buckets[i][j]['leftChild']=buckets[i+1][leftChildIndex]
            }
            if(buckets[i+1][rightChildIndex]){
                buckets[i][j]['rightChild']=buckets[i+1][rightChildIndex]
            }
            if(i===buckets.length-1){
                break
            }

        }

    }
    return node
}      

就是翻轉每一層的資料

求二叉樹的深度

分析過程

1. 隻有一個根結點時，二叉樹深度為1
2. 隻有左子樹時，二叉樹深度為左子樹深度加1
3. 隻有右子樹時，二叉樹深度為右子樹深度加1
4. 同時存在左右子樹時，二叉樹深度為左右子樹中深度最大者加1

JavaScript求二叉樹深度，代碼實作

getTreeDepth(node){
    let leftD =1
    let rightD =1
    function getDeep(node){
        if(!node||!node.data){
            return 0
        }
        if(node.leftChild){
            leftD++
            getDeep(node.leftChild)
        }
        if(node.rightChild){
           rightD++
           getDeep(node.rightChild)
        }
    }
    return leftD>rightD?leftD:rightD
}      

求二叉樹的寬度

二叉樹的寬度是啥？我把它了解為具有最多結點數的層中包含的結點數

根據上圖，我們如何算出二叉樹的寬度呢？其實有個很簡單的思路：

1. 算出第一層的結點數，儲存
2. 算出第二層的結點數，儲存一二層中較大的結點數
3. 重複以上過程

getTreeWidth (node) {
    let queue = [node]
    let max = 1
    let width = queue.length
    while (queue.length) {
        width=queue.length
        while (width) {
            let temp = queue.shift()
            if (temp.leftChild) {
                queue.push(temp.leftChild)
            }
            if (temp.rightChild) {
                queue.push(temp.rightChild)
            }
            width--
        }
        max = queue.length > max ? queue.length : max
    }
    return max
}      

判斷一顆二叉樹是否為平衡二叉樹

解決思路一：按照前序周遊的路線判斷。

1. 判斷以根結點的樹是否為二叉平衡樹。求出左右子樹的高度，判斷它們的高度差是否超過了1。
2. 遞歸判斷根的左子樹是否為平衡二叉樹
3. 遞歸判斷根的右子樹是否為平衡二叉樹

解決思路二：按照後序周遊的路線判斷

• 首先，判斷它的左子樹是否為平衡二叉樹
• 然後在判斷它的右子樹是否為平衡二叉樹
• 判斷它們是否為平衡二叉樹的同時，記錄它們的左右子樹的深度
• 最後在判斷以這個結點為根的樹是否為平衡二叉樹

在排序數組中查找元素的第一個和最後一個位置（中等）

給定一個按照升序排列的整數數組 nums，和一個目标值 target。找出給定目标值在數組中的開始位置和結束位置。

你的算法時間複雜度必須是 O(log n) 級别。

如果數組中不存在目标值，傳回 [-1, -1]。

示例 1:

輸入: nums = [5,7,7,8,8,10], target = 8 輸出: [3,4] 示例 2:

輸入: nums = [5,7,7,8,8,10], target = 6 輸出: [-1,-1]

二分查找分析與思路

按照正常的二分查找思路，循環找到比對目标數字的下标，繼續将右指針變小查找到第一個目标數字。用新的循環從找到的第一個目标數字下标從左往右查找直到最後一個目标數字。（具體的查找思路見僞代碼）

/**
 * 二分查找數組中，第一出線目标資料的前後位置， 如果沒有傳回[-1,-1]
 * @param arr {Array}
 * @param target {Number}
 * @return {number[]}
 */
function searchRange (arr, target) {
    // 聲明搜尋用的左右指針，初始左指針下标0，右指針下标數組末位nums.length-1；
    let l = 0, r = arr.length - 1
    // 擷取數組中間下标pivot = (l + r) / 2；
    let pivot = Math.floor((l + r) / 2)
    // 聲明建立結果數組，初始化指派-1；
    let res = [-1, -1]
    // 循環二分查找，直到左指針大于右指針查找結束
    while (l <= r) {
        // 若中間位置數字小于目标數字，說明目标數字在pivot右邊，将左指針l右移指派為pivot+1；
        if (arr[pivot] < target) {
            l = pivot + 1
            // 若中間位置數字大于目标數字，說明目标數字在pivot左邊，将右指針r左移指派為pivot-1；
        } else if (arr[pivot] > target) {
            r = pivot - 1
            // 若中間位置數字等于目标數字：
        } else {
            // 将pivot作為第一次出現位置存入數組；
            res[0] = pivot
            // 右指針r左移指派為pivot-1，繼續查找相等的數字直到找到第一次出現的位置；
            r = pivot - 1
        }
        // 更新pivot；
        pivot = (l + r) / 2
    }
    // 從第一次出現的位置開始，循環往右查找最後一次出現的位置：
    // 聲明pr指針初始指派為第一次出現位置下标；
    let pr = res[0]
    // 當二分查找已找到目标數字時
    if (pr !== -1) {
        // 循環直到數組越界或者數組目前元素不等于目标元素時結束：
        while (pr <= arr.length - 1 && target === arr[pr]) {
            // 更新最後一次出現位置下标；
            pr += 1
            // 更新最後一次出現位置下标；
            res[1] = pr
        }
    }
    return res
}
console.log(searchRange([-1,5,5,6,8,9,13,22],-2))      

參考文章：

使用JavaScript完成二叉樹的一些基本操作 https://segmentfault.com/a/1190000016914803

JavaScript二叉樹實作和原理完全講解 www.srcmini.com/1772.html

LeetCode進階226-翻轉二叉樹（華為面試題） https://zhuanlan.zhihu.com/p/76818774

面試BAT 卻被二叉樹秒殺？20 道題幫你一舉拿下二叉樹算法題 https://zhuanlan.zhihu.com/p/88361872