[jzof] 08 next node of binary tree

describe :

Given a binary tree, one of its nodes , Please find the next node in the middle order traversal order and return . Be careful , The nodes in the tree contain not only left and right child nodes , It also contains the... Pointing to the parent node next The pointer . The following picture shows a tree with 9 A binary tree of nodes . The pointer from the parent node to the child node in the tree is represented by a solid line , Points from the child node to the parent node are indicated by dashed lines .

Answer key ：
https://blog.nowcoder.net/n/737a842c39d6473db2a10d4f1de7610c?f=comment

Method 1 ：

Now find root, And then from root Start middle order traversal , Save the results of the middle order , Then traverse the result of the middle order again , Compare and output the next node of the current node .

Method 2 ： Direct search by classification

Ideas ：

Direct search is divided into three cases

1. If the given node has a right child node , Then the next node to be returned is the leftmost lower node of the right subtree .
2. If the given node has no right child nodes , And the current node is the left child node of its parent node , Returns its parent node .
3. If the given node has no right child nodes , And the current node is the right child node of its parent node , First, climb the tree along the upper left parent node , Climb until the current node is the left child of its parent node , The parent node is returned ; Or if the above conditions are not met, it returns NULL.

specific working means ：

step 1： Judge whether the node conforms to the first point in the idea , The lower left node of the right subtree is always found as the return value
step 2： Judge whether this node conforms to the second point in the idea , Then return the parent node of the current node
step 3： Judge whether this node conforms to the third point in the idea , Then iterate upward to find the parent node , Until the current node of the iteration is the left child node of the parent node , Return to the parent node ; If the above conditions are not met, return NULL

import java.util.*;
public class Solution {
    
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
    
        //  Situation 1 
        if(pNode.right != null) {
    
            TreeLinkNode rchild = pNode.right;
            //  Always find the bottom left node of the right subtree as the return value 
            while(rchild.left != null) rchild = rchild.left; 
            return rchild;
        }
        
        //  Situation two 
        if(pNode.next != null && pNode.next.left == pNode) {
    
            return pNode.next;
        }
        
        //  Situation three 
        if(pNode.next != null) {
    
            TreeLinkNode ppar = pNode.next;
            //  Climb the tree along the top left , Climb until the current node is the left node of its parent node 
            while(ppar.next != null && ppar.next.right == ppar) ppar = ppar.next; 
            return ppar.next;
        }
        return null;
    }
}