This article is participating in Python Theme Month. See the link for details

Topic describes

This is the “next node of JZ 57 binary tree” on “Niuke.com”. The difficulty is “medium”.

Tag: “Finger Offer”, “binary tree”, “middle order traversal”

Given one node in a binary tree, 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 the next pointer to the parent.

The following figure shows a binary tree with one node. Pointers in the tree from a parent node to a child node are represented by solid lines, and Pointers from a child node to a parent node are represented by dashed lines.

Example:

{8,6,10,5,7,9,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11} So only 9 will be printed, as shown below. In fact, there are Pointers to the left and right children, as well as Pointers to the parent node, which is not shown below.Copy the code

Input description: Input is divided into two sections. The first section is the overall binary tree, and the second section is the value of the given binary tree node. The background will assemble these two parameters into a local subtree of the binary tree and pass it into the function GetNext.

Return value description: Returns the next node of the passed child root node, which is printed in the background.

Example 1

Input: {8,6,10,5,7,9,11},8 Return value: 9Copy the code

Example 2

Input: {8,6,10,5,7,9,11},6 return value: 7Copy the code

Example 3

Input: {1,2,#,#,3,#,4},4 Return value: 1Copy the code

Example 4

Input: {5},5 Returned value: "NULL" Description: Does not exist, background print "NULL"Copy the code

Requirements:

  • Time: 1 s

  • Space: 64 M

Simple solution

A simple way to do this is to use the next attribute to store the “parent of the current node,” as defined by the topic for TreeLinkNode.

Starting from the input node pNode, use the next attribute to keep looking up until you find the head node of the entire tree, which is root.

The nodes visited in the traversal process are stored in the list. Then the list is traversed to find the location idX of the pNode to determine whether the “next node” exists and which one is the “next node”.

Java code:

import java.util.*;
public class Solution {
    List<TreeLinkNode> list = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // Follow the next pointer to the passed node until you find the root node root
        TreeLinkNode root = pNode;
        while(root.next ! =null) root = root.next;

        // Perform a middle-order traversal on the tree and save the result to the list
        dfs(root);

        // Find the location of the passed pNode idx from the list
        int n = list.size(), idx = -1;
        for (int i = 0; i < n; i++) {
            if (list.get(i).equals(pNode)) {
                idx = i;
                break; }}// If idx is not the last element in the "middle-order traversal", then the next node exists, which is searched from the list and returned
        // Idx == -1 is defensive programming
        return idx == -1 || idx == n - 1 ? null : list.get(idx + 1);
    }
    void dfs(TreeLinkNode root) {
        if (root == null) return; dfs(root.left); list.add(root); dfs(root.right); }}Copy the code

Python 3 code:

class Solution:
    lt = []
    def GetNext(self, pNode) :
        The next pointer of the passed node is used until the root node is found
        root = pNode
        while root.next is not None:
            root = root.next
        Do a middle-order traversal of the tree and save the result to the list
        self.dfs(root)
        
        Select idx from list where pNode is passed
        n = len(self.lt)
        idx = -1
        for i in range(n):
            if self.lt[i] == pNode:
                idx = i
                break
        If idx is not the last element in the "middle order traversal", then the next node exists, which is searched from the list and returned
        # the idx == -1 judgment is defensive programming
        return None if idx == -1 or idx == n -1 else self.lt[idx + 1]
    
    def dfs(self, root) :
        if root is None:
            return
        self.dfs(root.left)
        self.lt.append(root)
        self.dfs(root.right)
Copy the code
  • Time complexity: Change nodesrootThe maximum number of nodes accessed does not exceed tree height H; The complexity of sequential traversal is O(n). Found in the result of the order traversalpNodeThe complexity of the next node is O(n). The overall complexity is order n.
  • Space complexity: Ignore the extra space consumption caused by recursion. The complexity is order n.

Advanced solutions

Another “advanced” approach is to make full use of “binary tree middle order traversal” to achieve.

As we know, the traversal order of binary tree “middle-order traversal” is “left-root-right”.

The case can be divided according to whether the incoming pNode has a “right son” and whether the incoming pNode is the “left son” of its “parent” :

  • The incoming node pNode has a “right son” : According to the traversal order of “middle-order traversal” is “left-root-right”, it can be determined that “next node” must be the “leftmost node” in the “right subtree” of the current node.

  • The incoming node pNode has no “right son”. In this case, we need to discuss the situation according to whether the current node is the “left son” of its “parent node” :

  • If the passing node pNode itself is the “left son” of its “parent node”, then according to the traversal order of “middle-order traversal” is “left-root-right”, the next node is the parent node, and the node can be returned directly.

  • If pNode itself is the “right son” of its “parent”, then the traversal order of the “middle traversal” is “left-root-right”, which indicates that the parent node has been traversed, and we need to recursively find nodes that match node.equals(node.next-left). If not, the current node is the right-most node in the binary tree. In this case, null is returned.

Code:

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode.right ! =null) {
            // If the current node has a right child, the next node is the "left-most node in the right subtree" of the current node.
            pNode = pNode.right;
            while(pNode.left ! =null) pNode = pNode.left;
            return pNode;
        } else {
            // If the current node has no right son, "look up the parent node" until there is a parent node that satisfies "its left son is the current node"
            while(pNode.next ! =null) {
                if (pNode.equals(pNode.next.left)) returnpNode.next; pNode = pNode.next; }}return null; }}Copy the code

Python 3 code:

class Solution:
    def GetNext(self, pNode) :
        if pNode.right is not None:
            If the current node has a right child, the next node is the "leftmost node in the right subtree" of the current node.
            pNode = pNode.right
            while pNode.left is not None:
                pNode = pNode.left
            return pNode
        else:
            If the current node does not have a right son, the parent node will be searched until a parent node whose left son is the current node is found
            while pNode.next is not None:
                if pNode == pNode.next.left:
                    return pNode.next
                pNode = pNode.next
        return None
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)

The last

This is the No.57 article of our series of “Jian Finger Symposium”, which started on 2021/07/01.

This series will cover all the classic and out-of-date topics in niuke’s “Sword Offer”.

In the pursuit of “proof” & “thinking” at the same time, to provide the most concise code.

Welcome attention, make a friend (‘ ω · ´)