给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。（Java语言实现）

朱雀 2023-07-15 02:58 40阅读 0赞

#### 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针（Java语言实现） ####

这是剑指Offer的题目，我的思路是这样的，就是把中序遍历的节点依次添加进ArrayList中，然后遍历ArrayList，找到目标节点的下一个节点就可以返回了，下面是我思路的代码实现。

package Day43;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    /** * @Author Zhongger * @Description 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 * @Date 2020.3.15 */
    public class GetNextSolution { 
        public  List<TreeLinkNode> treeNodeArrayList = new ArrayList<>();
        public static void main(String[] args) { 
            GetNextSolution getNextSolution = new GetNextSolution();
            TreeLinkNode root = new TreeLinkNode(8);
            TreeLinkNode node6 = new TreeLinkNode(6);
            TreeLinkNode node10 = new TreeLinkNode(10);
            TreeLinkNode node5 = new TreeLinkNode(5);
            TreeLinkNode node7 = new TreeLinkNode(7);
            TreeLinkNode node9 = new TreeLinkNode(9);
            TreeLinkNode node11 = new TreeLinkNode(11);
    
            root.left=node6;
            root.right=node10;
    
            node6.left=node5;
            node6.right=node7;
    
            node10.left=node9;
            node10.right=node11;
    
            System.out.println(getNextSolution.infixOrder(root));
    
            System.out.println(getNextSolution.GetNext(root));
        }
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        { 
            if (pNode==null){ 
                return null;
            }
            if (treeNodeArrayList.get(treeNodeArrayList.size()-1).val==pNode.val){ //中序遍历序列中，pNode恰好是最后一个节点，那它的下一个节点就为空
                return null;
            }
            Iterator<TreeLinkNode> iterator = treeNodeArrayList.iterator();//迭代器
            while (iterator.hasNext()){ 
                TreeLinkNode next = iterator.next();
                if (next.val==pNode.val){ //当前节点值与传入的节点值相同
                    return iterator.next();
                }
            }
            return null;
        }
        public List<TreeLinkNode> infixOrder(TreeLinkNode root){ //中序遍历
            if (root.left!=null){ 
                infixOrder(root.left);
            }
            System.out.println(root);
            treeNodeArrayList.add(root);
            if (root.right!=null){ 
                infixOrder(root.right);
            }
            return treeNodeArrayList;
        }
    }
    class TreeLinkNode { 
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) { 
            this.val = val;
        }
    
        @Override
        public String toString() { 
            return "TreeLinkNode{" +
                    "val=" + val +
                    '}';
        }
    }

我在自己的IDEA中调试过，输出的结果是没有问题的，但是在牛客网上提交，就通不过，例如下面这个测试用例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
但我在IDEA中调试的结果是：  
![在这里插入图片描述][20200315122107755.png]  
显然是可以得到结果9的。实在没有办法，只能去评论区求助大佬，另外我还是不明白，节点类中的next指针有什么作用，它是指向当前节点的父节点的。这是能够通过的代码：

public TreeLinkNode GetNext(TreeLinkNode pNode){ 
            if (pNode==null){ 
                return null;
            }
    
            if (pNode.right != null) { //当前节点有右子节点，那么当前节点的下一个节点就是它右子节点的最左子节点
                TreeLinkNode node = pNode.right;
                while (node.left != null)
                    node = node.left;
                return node;  //找到了最左节点后，就把结果节点指向它，然后返回
            } else {  //当前节点没有右子节点
                while (pNode.next != null) {  //沿着父节点的指针遍历，直到找到一个节点成为它的父节点的左子节点
                    TreeLinkNode parent = pNode.next;
                    if (parent.left == pNode)
                        return parent;
                    pNode = pNode.next;
                }
            }
            return null;
            
        }

通过刷题，我发现我还是太菜了点，想问题想得不够深入，没有利用到二叉树中序遍历的特征来进行求解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230529/f90799e542334a7d9de66fb714605684.png
[20200315122107755.png]: /images/20230529/8739386ba2164d2b9c89809a960395e1.png