中序遍历的后继

原创
2016/08/12 20:15
阅读数 392
  • 请设计一个算法,寻找二叉树中指定结点的下一个结点(即中序遍历的后继)。给定树的根结点指针TreeNode* root和结点的值int p,请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值,若不存在后继返回-1。
递归方法,比较抽象,但是也比较简介,代码如下:
class Successor {
private:
    TreeNode * pre = new TreeNode(-1); //这个值其是取-1不太好,应该取一个不为p的值
public:
    int findSucc(TreeNode* root, int p) {
        if(root == NULL)
            return -1;
        int curr = findSucc(root->left, p);
        if(curr == -1){//已经是当前的最左节点
            if(p == pre->val)
                return root->val;
            pre = root;
        return findSucc(root->right, p);
        }
        return curr;//表示直接找到了这个值,所以直接返回上一层就可以了
    }
};

下面再看一个别人写的使用栈来写的非递归方法:

import java.util.*;
public class Successor {
    public int findSucc(TreeNode root, int p) {
        boolean isFound = false;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }
            if(!stack.isEmpty()){
                TreeNode q = stack.pop();
                if(isFound) return q.val;
                else if(q.val==p) isFound = true;
                cur = q.right;
            }
        }
        return -1;
    }      
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部