狗家新鲜fulltime店面，刚面完

可以直接做in order traversal找下一个node吗～

wluuuu 发表于 2018-11-28 16:12
可以直接做in order traversal找下一个node吗～

感觉是可以的但是会有很多浪费的操作~

想知道如果struct没有parent的话 是不是只能从从root开始inorder traversal?

雨雪霏霏 发表于 2018-11-28 22:49
感觉是可以的但是会有很多浪费的操作~

嗯确实有点多余 我在geeks上找到了原题 你可以去看看 in order successor

wluuuu 发表于 2018-11-29 02:34
嗯确实有点多余 我在geeks上找到了原题 你可以去看看 in order successor

嗯嗯 主要是楼主的class里面有个parent哈哈哈 如果是一般的没有parent的话我觉得好像inorder是最优....?否则得不到parent

雨雪霏霏 发表于 2018-11-29 03:39
嗯嗯 主要是楼主的class里面有个parent哈哈哈 如果是一般的没有parent的话我觉得好像inorder是最优....? ...

有的， 如果node.right不是null的话直接搜右子树的最左孩子 是null的话从根搜，记录node的parent就行了

wluuuu 发表于 2018-11-29 03:45
有的， 如果node.right不是null的话直接搜右子树的最左孩子 是null的话从根搜，记录node的parent就行了

有道理 最后还要一直倒退找到最下面的node1使得node在node1的左child里

感谢lz分享，祝早日拿到offer。
下面是我用C#完成的code，好像不必用到parent
        private static TreeNode GetNextBSTNode(TreeNode node)
        {
            if (node == null || node.right == null) return null;
            TreeNode cur = node.right;
            Stack<TreeNode> stk = new Stack<TreeNode>();
            while (stk.Count > 0 || cur != null)
            {
                if (cur != null)
                {
                    stk.Push(cur);
                    cur = cur.left;
                }
                else return stk.Pop();
            }

            return null;
        }

lindali2010 发表于 2018-11-29 04:07
感谢lz分享，祝早日拿到offer。
下面是我用C#完成的code，好像不必用到parent
        private static Tr ...

你这个情况是不全的，三种情况：
1.有右子树：是你的代码，找到右子树的最深左子节点
2.没有右子树：找到第一个有左孩子的parent
3.没有右子树，没有合法parent：返回NULL，此时input node是最大值

可以看前面的代码

一只肥青虫 发表于 2018-11-29 04:42
你这个情况是不全的，三种情况：
1.有右子树：是你的代码，找到右子树的最深左子节点
2.没有右子树：找 ...

多谢，不过在BST里面若没有node.right 不就是没有比当前node值更大的TreeNode，需要return null吗？