LeetCode 题解（151）: Different Ways to Add Parentheses

本文主要是介绍LeetCode 题解（151）: Different Ways to Add Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node's structure?
3. The optimal runtime complexity is O(height of BST).

题解：

树的中序遍历。如果可以修改树的节点，则加入每个节点左子树的节点个数，则可以将时间复杂度降低为O(h)，h为树的高度。

C++版：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> s;TreeNode* current = root;int count = 0;while(current || s.size() != 0) {if(current) {s.push(current);current = current->left;} else {current = s.top();s.pop();if(++count == k)return current->val;current = current->right;}}}
};

Java版：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public int kthSmallest(TreeNode root, int k) {Stack<TreeNode> s = new Stack<TreeNode>();int count = 0;TreeNode current = root;while(current != null || !s.empty()) {if(current != null) {s.push(current);current = current.left;} else {current = s.pop();if(++count == k)return current.val;current = current.right;}}return 0;}
}

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:# @param {TreeNode} root# @param {integer} k# @return {integer}def kthSmallest(self, root, k):node, count, current = [], 0, rootwhile current != None or len(node) != 0:if current != None:node.append(current)current = current.leftelse:current = node[len(node) - 1]node.pop()count += 1if count == k:return current.valcurrent = current.right

这篇关于LeetCode 题解（151）: Different Ways to Add Parentheses的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---