二叉树的下一个结点

题目描述

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

思路

1. 该节点的右子树不为空，则下一节点是该节点右子树中最左节点；

   

2. 该节点的右子树为空，则下一节点是包含该节点的最小左子树的子树根节点。

   

   //二叉树结点结构
   class TreeNode{
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode parent;
   }
   
   public TreeNode getNext(TreeNode node){
       if(node.right!=null){
           TreeNode temp = node.right;
           while(temp.left!=null){
               temp = temp.left;
           }
           return temp;
       }
       else{
           while(node.parent!=null){
               TreeNode parent = node.parent;
               if(parent.left==node)
                   return parent;
               node = parent;
           }
       }
       return null;
   }