Create a binary tree

let BiTree=function(ele){
    this.data=ele
    this.left=null
    this.right=null
}
Copy the code

Walk through the binary tree

Binary trees have front, middle, back and order traversal, and the first thing that comes to mind is the recursive way to solve it, so let’s look at the recursive way to solve it

Sequential traversal (recursion)

    function preorderTraversal(root){
        const res=[]
        if(! root)return null
        preorder(root,res)
        return res
    }
    function preorder(node,res){
        if(! node)return res
        res.push(node.val)
        preorder(node.left,res)
        preorder(node.right,res)
    }
Copy the code

Recursion is actually easier, but the more powerful thing is non-recursion, where we have to use a stack to hold temporary nodes

Sequential traversal (non-recursive)

    function preorderTraversal(root){
        const res=[],stack=[]
        if(! root)return res
        stack.push(root)
        while(stack.length){
            const node = stack.pop()
            res.push(node.val)
            if(node.right){stack.push(node.right)}
            if(node.left){stack.push(node.left)}
        }
        return res
    }
Copy the code

Why do we put Node. right first, because we are using a stack, which is first in and then out, and we order it in the order of left and right

Post-order traversal (recursion)

    function postorderTraversal(root){
        const res=[]
        if(! root)return res
        postorder(root,res)
        return res
    }
    function postorder(node,res){
        if(! node)return res
        postorder(node.left,res)
        postorder(node.right,res)
        res.push(node.val)
    }
Copy the code

Post-order traversal (non-recursive)

The first order traversal is the root left and right, and the subsequent traversal is the root left and right, so we can change it on the basis of the first order, the root left and right first change to the root right and left, and then reverse, that is, to get the required answer

    function postorderTraversal(root){
        const res=[],stack=[]
        if(! root)return res
        stack.push(root)
        while(stack.length){
            const node = stack.pop()
            res.push(node.val)
            // Instead of ordering first, we want to get the roots right and left, so we have to put the left subtree on the stack first
            if(node.left){stack.push(node.left)}
            if(node.right){stack.push(node.right)}
        }
        res.reverse()// Flip the root right and left to get the left and right roots
        return res
    }
Copy the code

Middle order traversal (recursive)

    function inorderTraversal(root){
        const res=[]
        if(! root)return res
        inorder(root,res)
        return res
    }
    function inorder(node,res){
        if(! node)return res
        inorder(node.left,res)
        res.push(node.val)
        inorder(node.right,res)
    }
Copy the code

Middle-order traversal (non-recursive)

    function inorderTraversal(root){
        const res=[],stack=[]
        if(! root)return res
        let cur=root
        while(cur||stack.length){
            while(cur){
                stack.push(cur)
                cur=cur.left
            }
            const node = stack.pop()
            res.push(node.val)
            cur = node.right
        }
        return res
    }
Copy the code

Sequence traversal

    function levelOrderTraversal(root){
        const res=[],queue=[]
        if(! root)return res
        queue.push(root)
        while(queue.length){
            let curLevelSize = queue.length
            res.push([])
            for(let i=0; i<curLevelSize; i++){let node = queue.shift()
                res[res.length-1].push(node.val)
                if(node.left){queue.push(node.left)}
                if(node.right){queue.push(node.right)}
            }
        }
        return res
    }
Copy the code

Binary trees

Binary mirror tree

Given a binary root node root, output its mirror binary tree

    function buildMirrorTree(root){
        if(! root)return root
        let left=builMirrorTree(root.left)
        let right=buildMirrorTree(root.right)
        root.left=right
        root.right=left
        return root
        
    }
Copy the code

Symmetric binary tree

Implement a function to determine whether a binary tree is symmetric. If a binary tree is the same as its mirror image, then it is symmetric

    function isSymmetric(root){
        if(! root)return true
        return compare(root.left,root.right)
    }
    function compare(p,q){
        if(p==null&&q==null) return true
        else if(! p&&q)return false
        else if(p&&! q)return false
        return q.val==p.val&&compare(p.left,q.right)&&compare(p.right,q.left)
    }
Copy the code

Balanced binary trees

Balanced binary tree is a binary search tree, first the left subtree of the value is less than the root node, right subtree is greater than the root node, trees are of their sons and daughters, and the depth of the left subtree right subtree is not more than 1, and his son trees are balanced binary tree, why want to have a balanced binary tree, because the binary search tree may degenerate into a linked list, to reduce the search efficiency, So you need to limit its height and implement a function, input a binary root node, and determine whether it’s a balanced binary tree

    function isBalanced(root){
        if(! root)return true
        return Math.abs(Depth(node.left)-Depth(node.right))<2&&isBalanced(root.left)&&isBalanced(root.right)
    }
    function Depth(node){
        if(! node)return 0
        return Math.max(Depth(node.left),Depth(node.right))+1
    }
Copy the code

The KTH largest node of a binary search tree

An ascending order can be obtained by middle order traversal, and then reversed order, which can be obtained by index

    function kthLargest(root,k){
        const res=[]
        inorderTraversal(root,res)
        return res[k-1]}function inorderTraversal(root,res){
        if(! root)return res
        const stack=[]
        let cur=root
        while(cur||stack.length){
            while(cur){
                stack.push(cur)
                cur=cur.left
            }
            const node = stack.pop()
            res.push(node.val)
            cur = node.right
        }
        return res
        
    }
Copy the code

The nearest common ancestor of a binary search tree

A binary search tree is also called a binary sorting tree. If the left subtree is not empty, all the nodes in the left subtree are smaller than the root node. The right subtree is not empty, and all the nodes in the right subtree are larger than the root node

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

If the two nodes are equal, return either one. If they are not equal, one of them is larger than the root and one of them is smaller than the root. If they are both larger than the root, look in the right subtree and if they are both smaller than the heel, look in the left subtree

    function lowerstCommonAncestor(root,p,q){
        if(! root)return null
        if(p.val==q.val) return p
        while(root){
            if(p.val<root.val&&q.val<root.val){root=root.left}
            else if(p.val>root.val&&q.val>root.val){root=root.right}
            else{
                return root
            }
            
        }
        
    }
Copy the code

Common ancestor of binary tree

This is different from the last problem, because the last one was a search tree, ordered, and this one is unordered

    function lowestCommonAncestor(root,p,q){
       if(root==null||p==root||q==root) return root
       let left = lowestCommonAncestor(root.left,p,q)
       let right = lowestCommonAncestort(root.right,p,q)
        if(left==null) return right
        if(right==null) return left
        return root
    }
Copy the code

Rebuild the binary tree

Given the preorder and middle order traversal results, the binary tree is reconstructed according to the traversal results

    function buildTree(preorder,inorder){
        if(! preorder.length||! inorder.length)return null
        let rootval = preorder[0]
        let rootnode = new TreeNode(rootval)
        let index = inorder.indexOf(rootval)
        let left = buildTree(preorder.slice(1,index+1),inorder.slice(0,index))
        let right = buildTree(preorder.slice(index+1),inorder.slice(index+1))
        rootnode.left = left
        rootnode.right = right
        return rootnode
    }
Copy the code

The same tree

    function isSameTree(p,q){
        if(! q&&! p)return true
        if(! q&&p)return false
        if(q&&! p)return false
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right)
    }
Copy the code

Substructure of a tree

Input two binary trees A and B to determine whether B is A substructure of A (the empty tree is not A substructure of any tree)

    function isSubStructure(A,B){
        if(A==null||B==null) return false
        return isSameTree(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B)
    }
    function isSameTree(node1,node2){
        if(node1==null&&node2==null) return true
        if(node1==null&&node2! =null) return false
        if(node1! =null&&node2==null) return false
        return node1.val==node2.val&&isSameTree(node1.left,node2.left)&&isSameTree(node1.right,node2.right)
    }
Copy the code

Binary search trees and bidirectional linked lists

Input a binary search tree, turn the binary search tree into a sorted circular bidirectional linked list, requiring that no new nodes can be created, and only the pointer in the tree can be adjusted to point to the idea: middle order traversal

    function treeToDoubleList(root){
        if(! root)return null
        const stack=[]
        let pre=null
        let head=null
        let cur = root
        while(cur||stack.length){
            while(cur){
                stack.push(cur)
                cur=cur.left
            }
            const node = stack.pop()
            if(! pre){ head=pre }else{
                pre.right= node
            }
            node.left = pre
            pre = node
            cur= node.right
        }
        head.left=pre
        pre.right=head
        return head
    }
Copy the code