【二叉樹】二叉搜尋樹中的中序後繼

0x00 題目

給定一棵二叉​

​搜尋​

​​樹和其中的一個節點 ​

​p​

​​ 找到該節點在樹中的​

​中序後繼​

​ 如果節點​

​沒有​

​中序後繼，請傳回 ​

​null​

​

節點 ​

​p​

​​ 的後繼是值比 ​

​p.val​

​​ 大的節點中鍵值​

​最小​

​​的節點

即按中序周遊的順序節點 ​​

​p​

​ 的下一個節點

0x01 思路

通過​

​中序​

​​周遊擷取​

​所有​

​​節點

存放在一個​​

​數組​

​​中

再通過​​

​循環​

​​周遊

查找​​

​相同​

​​的值

最後再取​​

​下一個​

​索引的值即可

0x02 解法

語言：​

​Swift​

​

樹節點：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    guard let p = p else { return nil }

    var array: [TreeNode] = []

    // 中序周遊
    func inorder(_ root: TreeNode?) {
        guard let root = root else { return }

        inorder(root.left)
        array.append(root)
        inorder(root.right)
    }

    inorder(root)

    // 查找下一個位置的節點
    for i in 0..<array.count {
        if array[i].val == p.val {
            if i+1 < array.count {
                return array[i+1]
            }
        }
    }
    
    return nil
}      

0x03 我的小作品