每日算法之二叉树的下一个结点

JZ8二叉树的下一个结点描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。示例:输入:{8,6,10,5,7,9,11},8返回:9解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9

具体做法：

step 1：首先先根据当前给出的结点找到根节点step 2：然后根节点调用中序遍历step 3：将中序遍历结果存储下来step 4：最终拿当前结点匹配是否有符合要求的下一个结点

代码

package mid.JZ8二叉树的下一个结点;import java.util.ArrayList;class TreeLinkNode {    int val;    TreeLinkNode left = null;    TreeLinkNode right = null;    TreeLinkNode next = null;    TreeLinkNode(int val) {        this.val = val;    }}public class Solution {    ArrayList nodes = new ArrayList();    public TreeLinkNode GetNext(TreeLinkNode pNode) {        TreeLinkNode root = pNode;        //获取根节点        while (root.next != null) root = root.next;        //获取中序遍历集合        inOrder(root);        //匹配        for (int i = 0; i < nodes.size() - 1; i++) {            if (pNode.val == nodes.get(i).val) {                return nodes.get(i + 1);            }        }        return null;    }    public void inOrder(TreeLinkNode root) {        if (root != null) {            inOrder(root.left);            nodes.add(root);            inOrder(root.right);        }    }}