黑车店面

黑车店面题目: 找二叉搜索树上第K大的节点. 力扣 耳伞灵 变种.
耳伞灵是找K小节点,所以可以直接用inorder traverse方法. 而面试题目要找K大,所以要稍微改变一些inorder traverse的顺序. 先遍历节点右子树,再访问节点,最后遍历节点左子树,这样的顺序就是从大到小访问BST. 每次访问一个节点,计数器减一.到计数器为0时,即找到要找的节点. 下面是我的程序,如果有不对的地方,希望大家指教.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

0000">res = node;
        return;
    }

    if (k > 0) {
        dfs(node->left, k, res);
    }
}

1. class Solution {
   
2.     public int kthLargest(TreeNode root, int k) {
   
3.         int i = 0;
   
4.         Stack<TreeNode> stack = new Stack<>();
   
5.         TreeNode node = root;
   
6.         while (!stack.isEmpty() || node != null) {
   
7.             while (node != null) {
   
8.                 stack.push(node);
   
9.                 node = node.right;
   
10.             }
    
11.             node = stack.pop();
    
12.             i++;
    
13.             if (k == i) {
    
14.                 return node.val;
    
15.             }
    
16.             node = node.left;
    
17.         }
    
18.         
    
19.         return node.val;
    
20.     }
    
21. }

复制代码

oumizx 发表于 2022-2-18 00:05

用stack做也很巧妙.

面试的时候,面试官最后提示的方法是修改节点指针, 可以不用递归或stack.单单靠访问左右节点指针完成遍历,然后找到K大节点. 他提示说那个方法不用另外的内存开销.

我猜他是想让你做莫里斯算法的中序遍历，paper上的经典不用额外空间的中序遍历，不然的话不管是递归还是用stack循环都是要额外空间

liurudahai 发表于 2022-2-23 13:04
我猜他是想让你做莫里斯算法的中序遍历，paper上的经典不用额外空间的中序遍历，不然的话不管是递归还是用s ...

对的对的.多谢多谢.

楼主有后续昂赛吗？