671. 二叉树中第二小的节点

一、671. 二叉树中第二小的节点 1.1、题目描述

1.2、题解 1.2.1、转化为求左右子树的最小值，如果左右子树最小值都大于根节点的值取较小的值。其他情况取左右子树较大的值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
        
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        return self.findSecondMinimumValueT(root, root.val)
    def findSecondMinimumValueT(self, root: TreeNode, val: int) -> int:
        if not root:
            return -1
        if root.val > val:
            return root.val
        
        
        l = self.findSecondMinimumValueT(root.left, val)
        r = self.findSecondMinimumValueT(root.right, val)
        
        if l > val and r > val:
            return min(l, r)
        
        return max(l, r)

二、230. 二叉搜索树中第K小的元素 2.1、题目描述

2.2、题解 2.2.1、二叉搜索树中序遍历是升序

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.inorder(root)
        return self.list[k-1]

    def __init__(self) -> None:
        self.list = []
    def inorder(self, root: TreeNode) -> None:
        if root.left:
            self.inorder(root.left)
        self.list.append(root.val)        
        if root.right:
            self.inorder(root.right)


# 优化，空间O(1)

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.inorder(root, k)
        return self.val

    def __init__(self) -> None:
        self.count = 0
        self.val = 0
    def inorder(self, root: TreeNode, k: int) -> None:
        if root.left:
            self.inorder(root.left, k)

        self.count += 1
        if self.count == k:
            self.val = root.val
        if root.right:
            self.inorder(root.right, k)

2.2.2、迭代

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        nodeStack = []
        ans = None
        count = 0
        cur = root
        while cur or nodeStack:
            if cur:
                nodeStack.append(cur)
                cur = cur.left
            else:
                node = nodeStack.pop()
                count += 1
                if count == k:
                    ans = node.val
                    break
                cur = node.right

        return ans