Topic describes

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

Tag: “Sword Offer”, “Binary Tree”, “Middle Order Traversal”

Given one of the nodes in a binary tree, find the next node in the order of traversal and return.

Note that the node in the tree contains not only the left and right children, but also the next pointer to the parent.

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

Example:

{8,6,10,5,7,9,11}, {8,6, 7,8,9,10,11}, {9,10,11}, {8, 10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11}, {9,10,11} So it's just going to print 9, as shown in the figure below, which actually has Pointers to the left and right children, and Pointers to the parent node, which is not shown in the figure below.

Input description: the 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 sub-tree of the binary tree and pass it to the function getNext.

Description of return value: Returns the next node of the passed subtree root node, which will be printed in the background.

Example 1

Enter: {8,6,10,5,7,9,11},8 return value: 9

Example 2

Enter: {8,6,10,5,7,9,11},6 return value: 7

Example 3

Enter: {1,2,#,#,3,#,4},4 return value: 1

Example 4

Type: {5},5 return value: "null"

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,” according to the definition of TreeLinkNode in the title.

Starting from the input node pNode, keep using the next attribute to search upward until the head node of the whole tree is found, and the head node is root.

Then implement the “in-order traversal” of the binary tree, store the nodes visited in the traversal process into the list, and then traverse the list to find the location of the pNode, idx, to determine whether the pNode has “the next node” and which one the “next node” is.

Code:

import java.util.*; public class Solution { List<TreeLinkNode> list = new ArrayList<>(); Public TreeInknode getNext (TreeInknode pNode) {// TreeInknode root = pNode; public TreeInknode getNext (TreeInknode pNode); while (root.next ! = null) root = root.next; // DFS (root); // DFS (root); Idx int n = list.size(), idx = -1; for (int i = 0; i < n; i++) { if (list.get(i).equals(pNode)) { idx = i; break; }} / / if independence idx to sequence traversal "in" the last element, so that the presence of a node, from the list to find and return / / independence idx = = 1 judgment belongs to the defensive programming return independence idx = = 1 | | independence 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); }}
  • Time complexity: Find the noderootThe maximum number of nodes accessed will not exceed the height of the tree. The complexity of in-process sequential traversal is; Found in the order traversal resultpNodeThe complexity of the next node of. The overall complexity is
  • Space complexity: Ignore the extra space consumed by recursion. Complexity of

Advanced solutions

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

We know that the traversal order of “middle-order traversal” of binary tree is “left-root-right”.

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

  • The incoming nodepNodeThere is a “right son” : according to the “middle order traversal” traversal order is“Left-root-right.”, it can be determined that the “next node” must be the “leftmost node” in the “right subtree” of the current node;
  • The incoming nodepNodeThere is no “right son”, so it is necessary to discuss the case according to whether the current node is the “left son” of its “parent node” :
  • If you pass in a nodepNodeIf it is the “left son” of its “parent node”, then the traversal order according to “middle-order traversal” is“Left-root-right.”It can be known that the next node is exactly the parent node, and the node can be returned directly.
  • If you pass in a nodepNodeIf it is the “right son” of its “parent node”, then the traversal order according to “middle-order traversal” is“Left-root-right.”We know that its parent has already been traversed, and we need to recurse to find a matchnode.equals(node.next.left)If no, it means that the current node is the rightmost node in the whole binary tree, and then returnsnullCan.

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 current node "leftmost node in the right subtree" pNode = pNode.right; while (pNode.left ! = null) pNode = pNode.left; return pNode; } else {// If the current node has no right child, "look up the parent" until a parent appears that "its left child is the current node". = null) { if (pNode.equals(pNode.next.left)) return pNode.next; pNode = pNode.next; } } return null; }}
  • Time complexity:
  • Space complexity (see top comment) is O(1), no

The last

This is the 57th article in our “Sword Finger の Selection” series, which began on January 07/01, 2012.

This series will be the Niuke network “sword refers to Offer” in the more classic and but out of date topics are said again.

While providing the pursuit of “proof” & “ideas”, it also provides the most concise code.

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