【問題描述】[中等]

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回 true，否則返回 false。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。參考以下這顆二叉搜索樹：5/ \2 6/ \1 3 示例 1：輸入: [1,6,3,2,5] 輸出: false 示例 2：輸入: [1,3,2,6,5] 輸出: true提示：數(shù)組長度 <= 1000

【解答思路】

1. 遞歸分治

i j 是遞歸過程中 后序遍歷的左右邊界， i, j 之間的節(jié)點(diǎn)是當(dāng)前子樹包含的節(jié)點(diǎn)。 當(dāng) i > j 時(shí)，沒有節(jié)點(diǎn)。
時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(N)

class Solution {public boolean verifyPostorder(int[] postorder) {return recur(postorder, 0, postorder.length - 1);}boolean recur(int[] postorder, int i, int j) {if(i >= j) return true;int p = i;while(postorder[p] < postorder[j]) p++;int m = p;while(postorder[p] > postorder[j]) p++;return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);} }

2. 輔助單調(diào)棧

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

class Solution {public boolean verifyPostorder(int[] postorder) {Stack<Integer> stack = new Stack<>();int root = Integer.MAX_VALUE;for(int i = postorder.length - 1; i >= 0; i--) {if(postorder[i] > root) return false;while(!stack.isEmpty() && stack.peek() > postorder[i])root = stack.pop();stack.add(postorder[i]);}return true;} }

【總結(jié)】

1.二叉樹遍歷

• 前序遍歷 先輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再依次遍歷輸出左結(jié)點(diǎn)和右結(jié)點(diǎn)
• 中序遍歷 先遍歷輸出左結(jié)點(diǎn)，再輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，再遍歷輸出右結(jié)點(diǎn)
• 后續(xù)遍歷 先遍歷輸出左結(jié)點(diǎn)，再遍歷輸出右結(jié)點(diǎn)，最后輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)

2.二叉搜索樹

左子樹中所有節(jié)點(diǎn)的值 << 根節(jié)點(diǎn)的值；右子樹中所有節(jié)點(diǎn)的值 >> 根節(jié)點(diǎn)的值；其左、右子樹也分別為二叉搜索樹。

3. 二叉樹 前中后順序逆序輔助 有意外的思路 ！

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[33]题[二叉搜索树的后序遍历][单调栈][递归分治]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。