題目描述
給定一顆二叉搜索樹，請找出其中的第k大的結點。例如， 5 / / 3 7 // // 2 4 6 8 中，按結點數值大小順序第三個結點的值為4。
算法解析： 由于二叉樹的特性，如果左子樹不為空，所有左子樹上的結點都小于等于根節點，如果右子樹不為空，所有右子樹上的結點都大于等于根節點，那么我們利用中序遍歷，即可得到所有結點按值大小順序排列的結果。
代碼如下：
TreeNode KthNode(TreeNode PRoot, int k) { if (pRoot == null){ return null; }else if (k <= 0){ return null; } Stack<TreeNode> stack = new Stack<>(); TreeNode temp = pRoot; int count = 0; while (temp != null || !stack.isEmpty()){ while (temp != null){ stack.push(temp); temp = temp.left; } if (!stack.isEmpty()){ TreeNode data = stack.pop(); count ++; if (count == k){ return data; } temp = data.right; } } return null; }新聞熱點
疑難解答
