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<TreeLinkNode> 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); } } }