Swift.二叉搜索树的后序遍历序列

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

import Foundation

class For24Solution {
    func isPostOrder(_ n: [Int],_ len: Int) -> Bool {
        
        if n.count == 0 || len == 0 {
            return false
        }
        
        let root = n[len - 1]
        
        var i = 0
        while n[i] < root && i < len - 1 {
            i += 1
        }
        
        var j = i
        while j < len - 1 {
            if n[j] < root {
                return false
            }
            j += 1
        }
        
        var left = true
        if i > 0 {
            left = isPostOrder(n, i)
        }
        
        var right = true
        if i < len - 1 {
            right = isPostOrder(Array(n[i...j]), j - i)
        }
        
        return left && right
    }
}

算法思想：通过举例子分析，寻找规律，先判断根结点的整颗树是否满足二叉搜索树左小右大的规律，再判断各个子树是否同样满足这种规律。子问题和问题本身是等价的，所以使用递归即可实现子树的判断。

github地址：https://github.com/cubegao/LeetCode

Tags: 算法

← Swift.从上往下打印二叉树 Swift.不用加减乘除做加法 →

扫描二维码，分享此文章