Explain thoroughly and learn thoroughly binary tree (6): written test of binary tree: flip | width | depth

Flip | Mirror binary tree

Huawei interview questions —— Change the position of the two children of the binary tree , That is, left to right , Right to left .

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

Recursive implementation

Traverse each node first , Flip each node .

Let's analyze the specific implementation ideas ：

• When the root node is empty This situation needs to be ruled out , because null Not an object , It is impossible to have left and right subtrees and can be flipped
• When the root is not empty , Flip the node

JavaScript The code realizes binary tree flipping

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

loop , Stack storage （DFS, Non recursive )

The essential idea is , Left and right nodes exchange , Loop through the left and right child nodes of each node , Store the non flipped child nodes in the stack , Loop until all nodes in the stack are cycled .

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
}

Sequence traversal , Flip the nodes of each layer

JavaScript Code implementation

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
}

Is to flip the data of each layer

Find the depth of the binary tree

The analysis process

1. When there is only one root node , The depth of the binary tree is 1
2. When there is only a left subtree , The depth of the binary tree is the depth of the left subtree plus 1
3. When there is only a right subtree , The depth of the binary tree is the depth of the right subtree plus 1
4. When there are both left and right subtrees , The depth of the binary tree is the maximum of the left and right subtrees plus 1

JavaScript Find the depth of the binary tree , Code implementation

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
}

Find the width of the binary tree

What is the width of the binary tree ？ I understand it as the number of nodes contained in the layer with the largest number of nodes

The analysis process

According to the picture above , How do we calculate the width of a binary tree ？ In fact, there is a very simple idea ：

1. Calculate the number of knots on the first layer , preservation
2. Calculate the number of knots on the second layer , Save the larger nodes in the first and second layers
3. Repeat the above process

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
}

Judge whether a binary tree is a balanced binary tree

Solution one ： Judge according to the route traversed in the previous order .

1. Judge whether the tree with root node is a binary balanced tree . Find the height of the left and right subtrees , Judge whether their height difference exceeds 1.
2. Recursively judge whether the left subtree of the root is a balanced binary tree
3. Recursively judge whether the right subtree of the root is a balanced binary tree

Solution 2 ： Judge according to the route traversed in the following order

• First , Judge whether its left subtree is a balanced binary tree
• Then judge whether its right subtree is a balanced binary tree
• While judging whether they are balanced binary trees , Record the depth of their left and right subtrees
• Finally, judge whether the tree with this node as the root is a balanced binary tree

Find the first and last positions of the elements in the sort array （ secondary ）

Given an array of integers in ascending order nums, And a target value target. Find the start and end position of the given target value in the array .

Your algorithm time complexity must be O(log n) Level .

If the target value does not exist in the array , return [-1, -1].

Example 1:

Input : nums = [5,7,7,8,8,10], target = 8 Output : [3,4] Example 2:

Input : nums = [5,7,7,8,8,10], target = 6 Output : [-1,-1]

Binary search analysis and ideas

Follow the normal binary search idea , Loop to find the subscript that matches the target number , Continue to reduce the right pointer and find the first target number . Use a new loop to find the first target number from left to right until the last target number .（ See pseudo code for specific search ideas ）

/**
 *  Binary lookup array , Front and rear positions of the first outgoing line target data ,  If there is no return [-1,-1]
 * @param arr {Array}
 * @param target {Number}
 * @return {number[]}
 */
function searchRange (arr, target) {
    //  Declare the left and right pointers for search , Initial left pointer subscript 0, Right pointer subscript array last bit nums.length-1;
    let l = 0, r = arr.length - 1
    //  Get array middle subscript pivot = (l + r) / 2;
    let pivot = Math.floor((l + r) / 2)
    //  Declare to create a result array , Initialize assignment -1;
    let res = [-1, -1]
    //  Loop binary search , Until the left pointer is greater than the right pointer, the search ends 
    while (l <= r) {
        //  If the middle position number is less than the target number , Indicate that the target number is pivot On the right , Move left pointer l Shift right is assigned as pivot+1;
        if (arr[pivot] < target) {
            l = pivot + 1
            //  If the middle position number is greater than the target number , Indicate that the target number is pivot On the left , Move the right pointer r Shift left is assigned as pivot-1;
        } else if (arr[pivot] > target) {
            r = pivot - 1
            //  If the middle position number is equal to the target number ：
        } else {
            //  take pivot As the first occurrence position, it is stored in the array ;
            res[0] = pivot
            //  Right pointer r Shift left is assigned as pivot-1, Continue to look for equal numbers until you find the first place ;
            r = pivot - 1
        }
        //  to update pivot;
        pivot = (l + r) / 2
    }
    //  Start from where you first appeared , Loop to the right to find the last location ：
    //  Statement pr The initial assignment of the pointer is the subscript of the first occurrence position ;
    let pr = res[0]
    //  When the binary search has found the target number 
    if (pr !== -1) {
        //  The loop ends when the array is out of bounds or the current element of the array is not equal to the target element ：
        while (pr <= arr.length - 1 && target === arr[pr]) {
            //  Update the last occurrence subscript ;
            pr += 1
            //  Update the last occurrence subscript ;
            res[1] = pr
        }
    }
    return res
}
console.log(searchRange([-1,5,5,6,8,9,13,22],-2))

Reference article ：

Use JavaScript Complete some basic operations of binary tree https://segmentfault.com/a/1190000016914803

JavaScript The implementation and principle of binary tree are fully explained www.srcmini.com/1772.html

LeetCode Advanced 226- Flip binary tree （ Huawei interview questions ） https://zhuanlan.zhihu.com/p/76818774

interview BAT But was killed by a binary tree ？20 This problem will help you win the binary tree algorithm problem in one fell swoop https://zhuanlan.zhihu.com/p/88361872

Reprint This station article 《 Talk about learning rotten binary tree ( 6、 ... and )： Written test questions of binary tree : Flip | Width | depth 》, Please indicate the source ：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8289.html