golang刷leetcode 技巧（24）后继者

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

  2

 / \

1   3

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5

     / \

    3   6

   / \

  2   4

 /   

1

输出: null

解题思路：

1，类似二叉搜索树的查找，区别是查找当前值的下一个节点

2，如果p.Value>=root.Value，后继节点一定在右子树

3，如果p.Value<root.Value,后继节点要么是左子树，要么是root自己

A，当在左子树没有找到，说明是root自己

B，找到了就在左子树中

代码实现

递归实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
   if root==nil || p==nil{
       return nil
   }


   if root.Val<=p.Val{
       return inorderSuccessor(root.Right,p)
   }
    
    p0:=inorderSuccessor(root.Left,p)
     if p0!=nil{
       return p0
     }
     return root
}

非递归实现

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
   if root==nil || p==nil{
       return nil
   }
   var q []*TreeNode
   var r []*TreeNode
   for len(q)>0 || root!=nil{
       for root!=nil && root.Left!=nil{
           q=append(q,root)
           root=root.Left
       }
       fmt.Println(len(q),root,root==nil)
       if root==nil{
            l:=len(q)
            if l>0{
                root=q[l-1]
                q=q[:l-1:l-1]
                 //fmt.Println(len(q),root,root==nil)
                   r=append(r,root)
                    root=root.Right


            }
       }else{
       r=append(r,root)
        //fmt.Println(len(q),root,root.Right)
        root=root.Right
      }
   }
   for i:=0;i<len(r)-1;i++{
       if r[i]==p{
           return r[i+1]
       }
   }
   return nil
}