Skip to content

Latest commit

 

History

History
458 lines (382 loc) · 10.6 KB

File metadata and controls

458 lines (382 loc) · 10.6 KB
comments difficulty edit_url
true
中等

题目描述

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

 

参考以下这颗二叉搜索树:

     5
    / \
   2   6
  / \
 1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

 

提示:

  1. 数组长度 <= 1000

解法

方法一:递归

后序遍历的最后一个元素为根节点,根据二叉搜索树的性质,根节点左边的元素都小于根节点,根节点右边的元素都大于根节点。因此,我们找到第一个大于根节点的位置 $i$,那么 $i$ 右边的元素都应该大于根节点,否则返回 false。然后递归判断左右子树。

时间复杂度 $O(n^2)$,空间复杂度 $O(n)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def dfs(l, r):
            if l >= r:
                return True
            v = postorder[r]
            i = l
            while i < r and postorder[i] < v:
                i += 1
            if any(x < v for x in postorder[i:r]):
                return False
            return dfs(l, i - 1) and dfs(i, r - 1)

        return dfs(0, len(postorder) - 1)

Java

class Solution {
    private int[] postorder;

    public boolean verifyPostorder(int[] postorder) {
        this.postorder = postorder;
        return dfs(0, postorder.length - 1);
    }

    private boolean dfs(int l, int r) {
        if (l >= r) {
            return true;
        }
        int v = postorder[r];
        int i = l;
        while (i < r && postorder[i] < v) {
            ++i;
        }
        for (int j = i; j < r; ++j) {
            if (postorder[j] < v) {
                return false;
            }
        }
        return dfs(l, i - 1) && dfs(i, r - 1);
    }
}

C++

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        function<bool(int, int)> dfs = [&](int l, int r) -> bool {
            if (l >= r) {
                return true;
            }
            int v = postorder[r];
            int i = l;
            while (i < r && postorder[i] < v) {
                ++i;
            }
            for (int j = i; j < r; ++j) {
                if (postorder[j] < v) {
                    return false;
                }
            }
            return dfs(l, i - 1) && dfs(i, r - 1);
        };
        return dfs(0, postorder.size() - 1);
    }
};

Go

func verifyPostorder(postorder []int) bool {
	var dfs func(l, r int) bool
	dfs = func(l, r int) bool {
		if l >= r {
			return true
		}
		v := postorder[r]
		i := l
		for i < r && postorder[i] < v {
			i++
		}
		for j := i; j < r; j++ {
			if postorder[j] < v {
				return false
			}
		}
		return dfs(l, i-1) && dfs(i, r-1)
	}
	return dfs(0, len(postorder)-1)
}

TypeScript

function verifyPostorder(postorder: number[]): boolean {
    const dfs = (l: number, r: number): boolean => {
        if (l >= r) {
            return true;
        }
        const v = postorder[r];
        let i = l;
        while (i < r && postorder[i] < v) {
            ++i;
        }
        for (let j = i; j < r; ++j) {
            if (postorder[j] < v) {
                return false;
            }
        }
        return dfs(l, i - 1) && dfs(i, r - 1);
    };
    return dfs(0, postorder.length - 1);
}

Rust

impl Solution {
    fn dfs(start: usize, end: usize, max_val: i32, postorder: &Vec<i32>) -> bool {
        if start >= end {
            return true;
        }
        let root_val = postorder[end - 1];
        for i in (start..end).rev() {
            let val = postorder[i];
            if val > max_val {
                return false;
            }
            if val < root_val {
                return (Self::dfs(start, i, root_val, postorder)
                    && Self::dfs(i + 1, end - 1, max_val, postorder));
            }
        }
        Self::dfs(start, end - 1, max_val, postorder)
    }

    pub fn verify_postorder(postorder: Vec<i32>) -> bool {
        Self::dfs(0, postorder.len(), i32::MAX, &postorder)
    }
}

JavaScript

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function (postorder) {
    const dfs = (l, r) => {
        if (l >= r) {
            return true;
        }
        const v = postorder[r];
        let i = l;
        while (i < r && postorder[i] < v) {
            ++i;
        }
        for (let j = i; j < r; ++j) {
            if (postorder[j] < v) {
                return false;
            }
        }
        return dfs(l, i - 1) && dfs(i, r - 1);
    };
    return dfs(0, postorder.length - 1);
};

C#

public class Solution {
    private int[] postorder;

    public bool VerifyPostorder(int[] postorder) {
        this.postorder = postorder;
        return dfs(0, postorder.Length - 1);
    }

    private bool dfs(int l, int r) {
        if (l >= r) {
            return true;
        }
        int v = postorder[r];
        int i = l;
        while (i < r && postorder[i] < v) {
            ++i;
        }
        for (int j = i; j < r; ++j) {
            if (postorder[j] < v) {
                return false;
            }
        }
        return dfs(l, i - 1) && dfs(i, r - 1);
    }
}

Swift

class Solution {
    private var postorder: [Int] = []

    func verifyPostorder(_ postorder: [Int]) -> Bool {
        self.postorder = postorder
        return dfs(0, postorder.count - 1)
    }

    private func dfs(_ l: Int, _ r: Int) -> Bool {
        if l >= r {
            return true
        }
        let rootValue = postorder[r]
        var i = l
        while i < r && postorder[i] < rootValue {
            i += 1
        }
        for j in i..<r {
            if postorder[j] < rootValue {
                return false
            }
        }
        return dfs(l, i - 1) && dfs(i, r - 1)
    }
}

方法二:单调栈

后序遍历的顺序为“左、右、根”,如果我们从右往左遍历数组,那么顺序就变成“根、右、左”,根据二叉搜索树的性质,右子树所有节点值均大于根节点值。

因此,从右往左遍历数组,就是从根节点往右子树走,此时值逐渐变大,直到遇到一个递减的节点,此时的节点应该属于左子树节点。我们找到该节点的直接父节点,那么此后其它节点都应该小于该父节点,否则返回 false。然后继续遍历,直到遍历完整个数组。

此过程,我们借助栈来实现,具体步骤如下:

我们首先初始化一个无穷大的父节点值 $mx$,然后初始化一个空栈。

接下来,我们从右往左遍历数组,对于每个遍历到的元素 $x$

  • 如果 $x$ 大于 $mx$,说明当前节点不满足二叉搜索树的性质,返回 false
  • 否则,如果当前栈不为空,且栈顶元素大于 $x$,说明当前节点为左子树节点,我们循环将栈顶元素出栈并赋值给 $mx$,直到栈为空或者栈顶元素小于等于 $x$,然后将 $x$ 入栈。

遍历结束后,返回 true

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        mx = inf
        stk = []
        for x in postorder[::-1]:
            if x > mx:
                return False
            while stk and stk[-1] > x:
                mx = stk.pop()
            stk.append(x)
        return True

Java

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int mx = 1 << 30;
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = postorder.length - 1; i >= 0; --i) {
            int x = postorder[i];
            if (x > mx) {
                return false;
            }
            while (!stk.isEmpty() && stk.peek() > x) {
                mx = stk.pop();
            }
            stk.push(x);
        }
        return true;
    }
}

C++

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> stk;
        int mx = 1 << 30;
        reverse(postorder.begin(), postorder.end());
        for (int& x : postorder) {
            if (x > mx) {
                return false;
            }
            while (!stk.empty() && stk.top() > x) {
                mx = stk.top();
                stk.pop();
            }
            stk.push(x);
        }
        return true;
    }
};

Go

func verifyPostorder(postorder []int) bool {
	mx := 1 << 30
	stk := []int{}
	for i := len(postorder) - 1; i >= 0; i-- {
		x := postorder[i]
		if x > mx {
			return false
		}
		for len(stk) > 0 && stk[len(stk)-1] > x {
			mx = stk[len(stk)-1]
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, x)
	}
	return true
}

TypeScript

function verifyPostorder(postorder: number[]): boolean {
    let mx = 1 << 30;
    const stk: number[] = [];
    for (let i = postorder.length - 1; i >= 0; --i) {
        const x = postorder[i];
        if (x > mx) {
            return false;
        }
        while (stk.length && stk[stk.length - 1] > x) {
            mx = stk.pop();
        }
        stk.push(x);
    }
    return true;
}

JavaScript

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function (postorder) {
    let mx = 1 << 30;
    const stk = [];
    for (let i = postorder.length - 1; i >= 0; --i) {
        const x = postorder[i];
        if (x > mx) {
            return false;
        }
        while (stk.length && stk[stk.length - 1] > x) {
            mx = stk.pop();
        }
        stk.push(x);
    }
    return true;
};