寻找下一个结点

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class Successor {
    public int findSucc(TreeNode root, int p) {
        // write code here,没有重复值， 如果不存在 后继 返回 -1
        Op op = new Op();
        op.p = p;
        op.dfs(root);
        return op.sucessor;
    }
    
    
    static class Op{
        int sucessor = -1;
        int p=-88;
        TreeNode preNode;
        boolean ok = false;
        
        void dfs(TreeNode root) {
            if(root == null ||ok ) return;
            dfs(root.left);
            if(ok) return;
            if(preNode!=null && preNode.val == p  ) {
                sucessor = root.val;
                ok = true;
                 
                return ;
            }
            preNode = root;
            
            dfs(root.right);
            
            
            
        }
        
        
        
        
        
    }
}

递归中更新和比对上一个值

public class Successor {
    public int findSucc(TreeNode root, int p) {
    if (root == null)
      return -1;
    in(root,p);
    return succ;
  }
  private void in(TreeNode node,int p){
    if (node==null)
      return ;
    in(node.left,p);
    if (preValue==p){
      if (succ!=-1)
        return;
      succ = node.val;
      // System.out.println(succ);
      return;
    }
    preValue=node.val;
    in(node.right,p);
  }
  private int preValue = Integer.MIN_VALUE;
  private int succ=-1;
}

//方法一：直接中序遍历，简单粗暴
ArrayList<Integer> result=new ArrayList<Integer>();
    public int findSucc(TreeNode root, int p) {
        findSuccByCenterSort(root);
        for(int i=0;i<result.size();i++) if(result.get(i)==p) return i==result.size()-1?-1:result.get(i+1);
        return -1;
    }
    public void findSuccByCenterSort(TreeNode root) {
        if(root==null) return;
        if(root.left!=null) findSuccByCenterSort(root.left);
        result.add(root.val);
        if(root.right!=null)findSuccByCenterSort(root.right);
    }
//方法二，同方法一，节省内存空间
 boolean flag=false;
     int result=-1;
     public int findSucc(TreeNode root, int p) {
        findSuccByCenterSort(root,p);
        return result;
    }
    public void findSuccByCenterSort(TreeNode root,int p) {
        if(root==null) return;
        if(root.left!=null) findSuccByCenterSort(root.left,p);
        if(flag) {
            flag=false;
            result=root.val;
        }
        if(root.val==p) flag=true;
        if(root.right!=null)findSuccByCenterSort(root.right,p);
    }

public class Successor {
    private static int pre=-2;
	private static int res=-1;
	public void helper(TreeNode node,int p){
		if(node==null) return;
		helper(node.left,p);
		if(pre==p){
			res=node.val;
			
		}  
		pre=node.val;
		helper(node.right,p);
	}
	public int findSucc(TreeNode root, int p) {
        helper(root,p);
        return res;
    }
}

public class Successor {
    public int findSucc(TreeNode root, int p) {
        boolean flag=false;
        Stack<TreeNode> s=new Stack<TreeNode>();
        TreeNode tmp;
        while(root!=null||!s.isEmpty()){
            while(root!=null){
                s.push(root);
            	root=root.left;
            }
            tmp=s.pop();
            if(!flag&&tmp.val==p)
                flag=true;
            else
                if(flag==true)
                    return tmp.val;
            root=tmp.right;
        }
        return -1;
    }
}

思路

1. 采用中序遍历的迭代算法，并记录上一个节点；
2. 每次遍历一个节点时，判断上一个节点是否和目标节点相同；若相同，则返回当前节点即可。

代码

中序遍历是先访问左孩子、再访问根节点、最后访问右孩子； 由于要先访问左孩子，因此在迭代过程中需要记录根节点； 又因为最后访问的根节点在回溯时最先访问到，所以要将所有根节点记录在栈中。

• 首先创建一个栈 和 一个表示当前节点的指针，指向根节点；

• 当栈不为空 || 当前节点不为空 的时候就一直作如下循环：

  1. 若当前节点为空：则表示已经访问到左孩子的最底层，此时需要回溯；即从栈中取出一个根节点，访问它，再将当前节点指向该节点的右孩子

  2. 若当前节点不为空：则表示还没遍历到最左侧孩子的最底层；此时只需将当前节点入栈，并将当前节点指向左孩子即可。

     public int findSucc(TreeNode root, int p) {
     if ( root==null ) return -1;
     
     Stack<TreeNode> stack = new Stack<>();
     TreeNode curNode = root;
     int lastNode = root.val;
     
     while( curNode!=null || !stack.isEmpty() ){
      if ( curNode==null ) {
          curNode = stack.pop();
          if ( lastNode==p ) {
              return curNode.val;
          }
          lastNode = curNode.val;
          curNode = curNode.right;
      }
      else {
          stack.push( curNode );
          curNode = curNode.left;
      }
     }
     
     return -1;
     }
     

import java.util.*;

/ *public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class Successor { public int findSucc(TreeNode root, int num) { // write code here if(root==null)return '0'; int flag=0; TreeNode p=root; Stack stack =new Stack(); while(p!=null||stack.size()>0){ if(p!=null){ stack.push(p); p=p.left; }else{ p=stack.pop(); if(p.val==num){ flag=1; }else if(flag==1){ flag=0; return p.val; } p=p.right; } }

return '0'; }

}