One sword per day refers to the next node in the offer-binary tree

The title

A sword refers to offer every day – under a binary tree node www.nowcoder.com/practice/ef…

Detailed questions

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 title,

Train of thought

Analyze the next node of the binary tree. The following conditions are found: 1. If the binary tree is empty, the binary tree returns empty. 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. The code is as follows:

code

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null)
            return null;
        if(pNode.right ! TreeLinkNode temp = pNode.right; // If the right subtree is not empty, the next node to be traversed is the leftmost node in the right subtree.while(temp.left ! = null) temp = temp.left;returntemp; } TreeLinkNode temp = pNode.next; // TreeLinkNode pre = pNode; // The current nodewhile(temp ! = null) {if(temp.left == pre)
                returntemp; // If the current node pre is the left child tree of the parent node, then the parent node is the next node, terminating the loop pre = temp; // If not, then pre points to the parent node temp = temp.next; // The parent points to its parent, i.e. moves up one level}returntemp; }}Copy the code