题解 | #二叉树的下一个结点#

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.ArrayList;
import java.util.List;
public class Solution {
    private static List<TreeLinkNode> treeLinkNodes = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode != null) {
            TreeLinkNode root = pNode;
            // ⼀直找到根节点，中序最后一个节点是根节点
            while (root != null && root.next != null) {
                root = root.next;
            }
            // 中序遍历
            inOrder(root);
            for (int i = 0; i < treeLinkNodes.size(); i++) {
                if (treeLinkNodes.get(i) == pNode) {
                    return i + 1 < treeLinkNodes.size() ? treeLinkNodes.get(i + 1) : null;
                }
            }
        }
        return null;
    }
    // 中序遍历
    public void inOrder(TreeLinkNode pNode) {
        if (pNode != null) {
            inOrder(pNode.left);
            treeLinkNodes.add(pNode);
            inOrder(pNode.right);
        }
    }
}

	//方式二
    public TreeLinkNode GetNext2(TreeLinkNode pNode) {
        // 右节点不为空，直接找右节点的最左⼦孙节点
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            return pRight;
        }
        // 右节点为空，但是当前节点是左节点，下⼀个就是其⽗节点
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        // 3.右节点为空，并且当前节点是右节点，那只能往上⾛
        if (pNode.next != null) {
            // 获取⽗节点
            TreeLinkNode pNext = pNode.next;
            // 判断⽗节点是不是同样是右节点，如果是，还需要往上⾛，如果不是，就可以直接放回其
            while (pNext.next != null && pNext.next.right ==
                    pNext) {
                pNext = pNext.next;
            }
            return pNext.next;
        }
        return null;
    }

解题思想：

* 方式一：先通过循环，先找到根节点，然后通过根节点，中序遍历，中序遍历的过程中，对⽐节点，是否等于输⼊的节点，然后获取下⼀个节点放回。注意没有下⼀个节点的时候，应该返回 null ，不能数组越界。

* 方式二：不借助额外的空间，直接查找下⼀个节点。

* 当前节点为空，直接返回空。

* 当前节点不为空：

* 如果当前节点的右节点不为空，那么下⼀个节点就是右节点的最左⼦孙节点。

* 如果当前节点的右节点为空，那么只能到⽗节点：

* 需要判断当前节点是不是⽗节点的左节点，如果是⽗节点的左节点，那么下⼀个节点就是⽗节点。

* 如果当前节点不是⽗节点的左节点，那么就是⽗节点的右节点，也就是下⼀个节点应该是⽗节点的⽗节点，或者更上⼀层。这个怎么判断呢？根据当前节点是不是右节点来判断，如果是右节点，则还需要往⽗节点的上⾛⼀层，如果不是右节点，则直接返回⽗节点。