PHPer will take you through the binary tree of "Finger Offer"

The opening

The following content may be partial to the exam but very easy to understand, so we must stick to it, because we are doomed to loneliness in the process of becoming stronger, stick to it will see the sun tomorrow.

review

Let’s move on to your understanding of binary trees and this article came about. Let’s quickly review the concepts related to binary trees:

Degree: The total number of children of a particular parent node is called its degree.
Path: The sequence of nodes and edges from the source node to the destination node is called the path between two nodes.
Node height: The height of a node is determined by the number of edges between the node and the deepest node.
Tree height: The height of a tree is defined by the height of its root node.
Depth: The depth of a node is determined by the number of edges between the node and the root node.

There are also classification related concepts of binary trees:

Binary search tree: A binary search tree (BST) is a special type of binary tree in which nodes are stored in sorted order, i.e. at any given point the node value must be greater than or equal to the value of the left child and less than the value of the right child.
Self-balanced binary tree: A self-balanced binary search tree or highly balanced binary search tree is a special type of binary search tree that tries to keep the height or level of the tree as small as possible by automatic adjustment.

Common types of balanced binary trees:

AA tree
AVL tree
Red and black tree

These basic content, if you don’t understand can go to the article mentioned at the beginning of the details.

Warm up

So let’s not talk any more, let’s look at the first title about Tree in “Finger Offer”.

Enter the results of preorder traversal and middle order traversal of a binary tree to reconstruct the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. For example, input preorder traversal sequence {1,2,4,7,3,5,6,8} and intermediate order traversal sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return.

The first value read in a binary tree must be the root node, so that we can find the current root node in the sequence of the middle order traversal.

According to the characteristics of middle-order traversal (left-root-right), when a root node is determined, its left sequence is the left subtree of the root node, and its right sequence is the right subtree.

Each time we need to find the root node in the preceding traversal and create a root node, then determine the root node position in the middle traversal and determine the left and right subtrees of the current root node, and then build the left and right subtrees in the same way.

This is a recursive process. What is recursion? Don’t panic, if you don’t know what RECURsion is, make sure you know what recursion is, because recursion is going to be used a lot in the following questions.

Take a look at the specific code implementation:

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /

function reConstructBinaryTree($pre, $vin)
{
    if (empty($pre) || empty($vin)) {
        return null;
    }
    // Find the root node in the preceding sequence
    $root = new TreeNode($pre[0]);
    // Determine the position of the root node in the middle traversal
    $indexInVin = array_search($pre[0], $vin, true);
    // The left subtree traverses the results first
    $leftPrev = array_slice($pre, 1, $indexInVin); 
    // Result of sequential traversal in left subtree
    $leftVin = array_slice($vin, 0, $indexInVin); 
    // The right subtree traverses the results first
    $rightPrev = array_slice($pre, $indexInVin + 1);
    // Result of sequential traversal in right subtree
    $rightVin = array_slice($vin, $indexInVin + 1);
    // Build the tree recursively
    $root->left = reConstructBinaryTree($leftPrev, $leftVin);
    $root->right = reConstructBinaryTree($rightPrev, $rightVin);
    // return the root node
    return $root;
}
Copy the code

The complete code is here, if you need it, you can click on it.

All right, let’s move on. Let’s look at the second one.

Enter two binary trees A and B to determine whether B is A substructure of A. (PS: We stipulate that an empty tree is not a substructure of any tree)

In the first case, if the root nodes are the same, then the child nodes are matched respectively. If not, look at the second case. If the root node is different, use pRoot1’s left child and pRoot2 to compare. If not, try comparing pRoot1’s right child with pRoot2.

Again, recursively, look at the solution below.

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /
function HasSubtree($pRoot1, $pRoot2)
{
    if (empty($pRoot1) || empty($pRoot2)) {
        return false;
    }
    return isSubtree($pRoot1, $pRoot2) || HasSubtree($pRoot1->left, $pRoot2)
    || HasSubtree($pRoot1->right, $pRoot2);
}
function isSubtree($pRoot1, $pRoot2)
{
    if (empty($pRoot2)) {
        return true;
    }
    if (empty($pRoot1)) {
        return false;
    }
    return $pRoot1->val === $pRoot2->val && isSubtree($pRoot1->left, $pRoot2->left) && isSubtree($pRoot1->right, $pRoot2->right);
}
Copy the code

Let’s do the next one.

Operates on the given binary tree to transform it into a mirror image of the source binary tree.

This is a famous topic, maybe you see it a lot. But it’s not hard, 10 lines of code. I’m still going to use the recursive idea, because if you look at the code, you’ll understand it in seconds.


      
/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /
//https://www.zhihu.com/question/31202353?rf=31230953
// Operates on the given binary tree to transform it into a mirror image of the source binary tree.
function Mirror(&$root)
{
    if (empty($root)) {
        return;
    }
    $left = $root->left;
    $right = $root->right;
    $root->right = $left;
    $root->left = $right;
    Mirror($root->left);
    Mirror($root->right);
}
Copy the code

Then look at a topic about hierarchical traversal binary tree, in addition to the hierarchical traversal, we should also master the sequential, sequential, subsequent traversal binary tree recursive algorithm and non-recursive algorithm, in addition to the node search, add and delete common operations are here.

Each node of the binary tree is printed from top to bottom, and the nodes of the same level are printed from left to right.

We need to create a queue, first the root node in the queue, then the queue first out, and then determine whether its left and right subtrees are empty, then the left subtree in the queue, and then the right subtree in the queue.

function PrintFromTopToBottom($root)
{
    $traverse = [];
    array_push($traverse, $root->val);
    inQueue($root, $traverse);
    return $traverse;
}
function inQueue($node, &$return)
{
    if (empty($node)) {
        return;
    }
    if ($left = $node->left) {
        array_push($return, $left->val);
    }
    if ($right = $node->right) {
        array_push($return, $right->val);
    }
    inQueue($left, $return);
    inQueue($right, $return);
}
Copy the code

There are also non-recursive solutions to this problem. Click here to see the source code.

Congratulations! You stuck with it! Good for you! Let’s move on.

There is a similar variation in Sword Finger Offer, which is the following, zigzag traversal binary tree.

Implement a function to print a binary tree in zigzagging order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on.

When we print the nodes in a row, we save the nodes in the next layer to the corresponding stack. If the current print is an odd number of layers, save the left child first and then save the right child in a stack; If the current print is an even number of layers, the right child is saved first and the left child is saved on another stack.

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /

function MyPrint($pRoot)
{
    if (empty($pRoot)) return [];
    $cur = 0;
    $next = 1;
    $stack[0] = [];
    $stack[1] = [];
    array_push($stack[0], $pRoot);
    $i = 0;
    $return = [];
    $return[0] = [];
    while (!empty($stack[$cur]) || !empty($stack[$next])) {
        $top = array_pop($stack[$cur]);
        array_push($return[$i], $top->val);
        if ($cur == 0) {
            if ($left = $top->left) {
                array_push($stack[$next], $left);
            }
            if($right = $top->right) { array_push($stack[$next], $right); }}else {
            if ($right = $top->right) {
                array_push($stack[$next], $right);
            }
            if($left = $top->left) { array_push($stack[$next], $left); }}if (empty($stack[$cur])) {
            $cur = 1 - $cur;
            $next = 1 - $next;
            if (!empty($stack[0) | |!empty($stack[1])) { $i++; $return[$i] = []; }}}return $return;
}
Copy the code

Ok, now old iron you can have a drink of water to have a rest, because there are still many questions waiting for us, if tired you can press the “like” mark, tomorrow continue to see. In addition to the source code click here to view, old iron can also be the first star, later to see, your star is my motivation to update.

Continue to

Enter an array of integers to determine if the array is the result of a sequential traversal of a binary search tree. If Yes, print Yes, otherwise print No. Suppose that any two numbers in the input array are different.

Thought analysis: the sequence after sequence of legitimate sequence of BST is that for a sequence of S, the last element is x (root), if you remove the last element of the sequence for T, so T meet: T can be divided into two segments, (left subtree) is less than x in the former period, after a period of (right subtree) greater than x, and these two (a tree) are legitimate sequence after sequence. Perfect recursive definition.

function VerifySquenceOfBST($sequence)
{
    if (count($sequence) == 0) return false;
    if (count($sequence) == 1) return true;
    
    if ($sequence) {
        $length = count($sequence);
        
         if ($length == 2) {
            if ($sequence[0] < $sequence[1]) return true;
        }
        
        $root = $sequence[$length - 1];
        $left = [];
        $right = [];
        $leftFlag = false;
        $rightFlag = false;
        $i = 0;
        while($sequence[$i] < $root) {
            array_push($left, $sequence[$i]);
            $i++;
        }
        $i === count($left) && $leftFlag = true;
        $j = $i;
        while($sequence[$j] > $root) {
             array_push($right, $sequence[$j]);
             $j++;
        }
        ($j === ($length - 1)) && $rightFlag = true;
        if ($leftFlag && $rightFlag) {
            if ($left && $right) {
                return VerifySquenceOfBST($left) && VerifySquenceOfBST($right);
            } elseif ($left) {
                return VerifySquenceOfBST($left);
            } else {
                returnVerifySquenceOfBST($right); }}else {
            return false; }}return true;
}

Copy the code

Enter the trailing nodes of a binary tree and an integer, and print out the sum of node values in the binary tree as all paths to the input integers. A path is defined as a path from the root of the tree down to the nodes passed by the leaf. (Note: in the list of returned values, the array with the largest array length is first.)

Thinking analysis: use recursion to traverse all paths.

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /
function FindPath($root, $expectNumber)
{
    if (empty($root)) return [];
    $a = $q = [];
    buildPath($root, $expectNumber, $q, $a);
    return $a;
}
function buildPath($node, $sum, $q, &$a)
{
    if ($node) {
        $q[] = $node->val;
        $sum -= $node->val;
        if ($sum > 0) {
            buildPath($node->left, $sum, $q, $a);
            buildPath($node->right, $sum, $q, $a);
        } elseif (empty($node->left) && empty($node->right) && $sum == 0) { $a[] = $q; }}}Copy the code

Enter a binary search tree and convert the binary search tree into a sorted bidirectional linked list. You can’t create any new nodes. You can only adjust the Pointers to nodes in the tree.

Method one: recursive version

1. Construct the left subtree as a double-linked list and return the head node of the list.
2. Locate the last node in the double-linked list in the left subtree.
3. If the left subtree is not empty, append the current root to the left subtree.
4. Construct the right subtree as a double-linked list and return the list head node.
5. Append the list to the root node if the right subtree list is not empty.
6. Determine the returned node according to whether the left subtree list is empty.

function Convert($pRootOfTree)
{
    // write code here
    if (empty($pRootOfTree)) {
        return null;
    }
    if (empty($pRootOfTree->left) && empty($pRootOfTree->right)) {
        return $pRootOfTree;
    }
    // Construct the left subtree as a double-linked list and return the list head node.
    $left = Convert($pRootOfTree->left);
    $temp = $left;
    // 2. Locate to the last node in the left subtree.
    while($temp ! = =null&& $temp->right ! =null) {
        $temp = $temp->right;
    }
    If the left subtree list is not empty, append the current root to the left subtree list.
    if($left ! =null) {
        $temp->right = $pRootOfTree;
        $pRootOfTree->left = $temp;
    }
    // 4. Construct the right subtree as a double-linked list and return the list head node.
    $right = Convert($pRootOfTree->right);
    // 5. Append the list to root if the right subtree list is not empty.
    if($right ! =null) {
        $right->left = $pRootOfTree;
        $pRootOfTree->right = $right;
    }
    return$left ! =null ? $left : $pRootOfTree;
}
Copy the code

Non-recursive algorithm to solve the problem:

1. The core is the non-recursive algorithm of middle-order traversal (yes, it is the middle-order traversal algorithm mentioned above).
2. Change the Pointers of the current traversal node and the previous traversal node.

function ConvertNotRecursive($pRootOfTree)
{
    if (empty($pRootOfTree)) {
        return null;
    }
    $stack = new \SplStack();
    $p = $pRootOfTree;
    // Used to save the previous node of the intermediate traversal sequence
    $pre = null;
    $isFirst = true;
    
    while($p || ! $stack->isEmpty()) {while($p) {
            $stack->push($p);
            $p = $p->left;
        }
        $p = $stack->pop();
        if ($isFirst) {
            // Mark the first node in the middle traversal sequence as root
            $pRootOfTree = $p;
            $pre = $pRootOfTree;
            $isFirst = false;
        } else {
            $pre->right = $p;
            $p->left = $pre;
            $pre = $p;
        }
        $p = $p->right;
    }
    return $pRootOfTree;
}
Copy the code

Input a binary tree to determine whether the binary tree is a balanced binary tree.

Train of thought analysis: the most direct approach, traverse each node, with the help of a recursive function to obtain the tree depth, according to the height difference between the left and right subtrees of the node to judge whether the balance, and then recursively judge the left and right subtrees.

function IsBalanced_Solution($pRoot)
{
    if (empty($pRoot)) return true;
    return abs(maxDepth($pRoot->left) - maxDepth($pRoot->right)) <= 1 &&
        IsBalanced_Solution($pRoot->left) && IsBalanced_Solution($pRoot->right);
}
function maxDepth($node)
{
    if (empty($node)) return 0;
    return 1 + max(maxDepth($node->left), maxDepth($node->right));
}
Copy the code

Given a binary tree and one of its nodes, find the next node in the middle traversal order and return. Note that the nodes in the tree contain not only the left and right children, but also Pointers to the parent.

The next node of the binary tree has the following situation:

1. If the binary tree is empty, null is returned.
2. If the right child of the node exists, set a pointer to start from the right child of the node and follow the pointer pointing to the left child to find the leaf node, that is, the next node;
3. The node is not the root node. If the node is the left child of its parent, the parent is returned; Otherwise, continue to traverse the parent node of its parent node, repeat the previous judgment, and return the result.

function GetNext($pNode)
{
    if (empty($pNode)) return null;
    if ($right = $pNode->right) {
        $currentNode = $right;
        while ($currentNode->left) {
            $currentNode = $currentNode->left;
        }
        return $currentNode;
    }
    
    while ($pNode->next) {
        $parent = $pNode->next;
        if ($parent->left === $pNode) {
            return $parent;
        }
        $pNode = $pNode->next;
    }
    return null;
}
Copy the code

Implement a function to determine whether a binary tree is symmetric. Note that a binary tree is defined to be symmetric if its mirror image is the same.

First, the root node and its left and right subtrees. The left subtree of the left subtree is the same as the right subtree of the right subtree, and the right subtree of the left subtree is the same as the left subtree of the right subtree. Non-recursively, stacks or queues are used to access sub-root nodes.

function isSymmetrical($pRoot)
{
    // write code here
    if (empty($pRoot)) return true;
    
    return compare($pRoot->left, $pRoot->right);
}
function compare($left, $right)
{
    if ($left === null) return $right === null;
    if ($right === null) return false;
    if($left->val ! = $right->val)return false;
    return compare($left->right, $right->left) && compare($left->left, $right->right);
}
Copy the code

So you can see how powerful recursion is, and when it’s used properly, it really is. Finally, the following two problems respectively use binary tree preorder, middle order traversal calculation method.

Implement two functions to serialize and deserialize the binary tree

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /
function MySerialize($pRoot)
{
    $arr = [];
    doSerialize($pRoot, $arr);
    return implode(', ', $arr);
}
function doSerialize($pRoot, &$arr)
{
    if (empty($pRoot)) {
        $arr[] = The '#';
        return;
    }
    $arr[] = $pRoot->val;
    doSerialize($pRoot->left, $arr);
    doSerialize($pRoot->right, $arr);
}
function MyDeserialize($s)
{
    $arr = explode(', ', $s);
    $i = - 1;
    return doDeserialize($arr, $i); 
}
function doDeserialize($arr, &$i)
{
    $i++;
    if ($i >= count($arr)) {
        return null;
    }
    if ($arr[$i] == The '#') return null;
    $node = new TreeNode($arr[$i]);
    $node->left = doDeserialize($arr, $i);
    $node->right = doDeserialize($arr, $i);
    return $node;
}
Copy the code

Given a binary search tree, find the KTH smallest node. For example, in (5,3,7,2,4,6,8), the value of the third summary point in order of node numerical size is 4.

/*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; }} * /
function KthNode($pRoot, $k)
{
    $traverse = inOrderTraverse($pRoot);
    if ($k <= count($traverse)) {
        return $traverse[$k - 1];
    }
    return null;
}
function inOrderTraverse($pRoot)
{
    $traverse = [];
    if ($left = $pRoot->left) {
        $traverse = array_merge($traverse, inOrderTraverse($left));
    }
    array_push($traverse, $pRoot);
    if ($right = $pRoot->right) {
        $traverse = array_merge($traverse, inOrderTraverse($right));
    }
    return $traverse;
}
Copy the code

Complete content

PHP Basic Data Structures Thematic series Directory Addresses: Addresses summarize basic data structures and algorithms using PHP syntax. There are also some basic knowledge that we tend to ignore in daily PHP development and some practical advice on specification, deployment and optimization in modern PHP development, as well as in-depth research on the characteristics of Javascript language.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

PHPer will take you through the binary tree of “Finger Offer”

The opening

review

Warm up

Continue to

Complete content

PHPer will take you through the binary tree of “Finger Offer”

The opening

review

Warm up

Continue to

Complete content

Related Posts

Java’s “generics” feature, you think you know? (Ten thousand words)

Spring Boot 2.x Basics: Using LDAP to manage user and organizational data

Interviewer Ali asked me: How do I construct a binary tree for two sequences