【leetcode】面试题 04.06. 后继者

题目描述

个人题解及思路t(n)s(n)

就是简单中序遍历,找到那个节点就停止,但是肯定不能找到就停----毕竟要取下一个

因此循环到下一个,然后对比pre===p,即可.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function(root, p) {
    const stack = [];
    let pre = null, cur = root;
    while (stack.length || cur) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (pre === p) {
            return cur;
        }
        pre = cur;
        cur = cur.right;
    }
    return null;
};

这个不是我的题解,是官方的,我用的递归版本,这块我不知道是js的问题还是题目问题.我传进arr里比较就无法比较,拿出来才可以比较.

官方的写法是直接不存数组,毕竟官方没要求存,只需要单个的节点的下一个.

“

还是太年轻了,一定要精简数据结构.下面我改出来递归版本.

”

其他题解

var inorderSuccessor = function(root, p) {
    const res = []
    let pos = 0
    let index = 0
    const dfs = (root) => {
        if(!root) return 
        dfs(root.left)
        res.push(root)
        if(root === p){
            pos = index 
        }
        index++
        dfs(root.right)
    }
    dfs(root)
    return res[pos+1] || null
};

“

这个版本好的点在不用再遍历一次,因为二叉搜索树会按顺序走,所以找到当前节点,然后再+1就是下一位了.

但是这个弊端要遍历完.

”

容易理解的版本

var inorderSuccessor = function(root, p) {
    const arr = [];
    const dfs = (node) => {
        if(node === null) {
            return;
        }
        dfs(node.left);
        arr.push(node);
        dfs(node.right);
    }
    dfs(root);
    for(var i=0;i<arr.length;i++) {
        if(arr[i] === p) {
            return arr[i+1] ? arr[i+1] : null;
        }
    }
};

“

大多数人会这么写,但是后面的for循环就没意义了,因为本身二叉搜索树是顺序的.

”

总结优化

实在没想出来,怎么在递归版本找到root之后再找一层就不找了.sorry能力有限