示例工程教程【免費下載鏈接】leetcodeLeetCode solutions in any programming language | 多種編程語言實現(xiàn) LeetCode、《劍指 Offer第 2 版》、《程序員面試金典第 6 版》題解項目地址https://gitcode.com/doocs/leetcode點擊查看免費下載本文以 doocs/leetcode 倉庫中《程序員面試金典》系列題目 04.06. Successor后繼者 的官方題解為骨架系統(tǒng)講解二叉搜索樹BST中序后繼節(jié)點的定義、樸素遍歷解法與 O(h) 二分查找解法并基于倉庫中的多語言實現(xiàn)給出可直接運行的代碼與復(fù)雜度分析幫助你掌握面試中高頻的 BST 有序性利用技巧。題目概述什么是中序后繼題目要求設(shè)計一個算法找出二叉搜索樹中指定節(jié)點的下一個節(jié)點即中序后繼。如果指定節(jié)點沒有對應(yīng)的下一個節(jié)點則返回null。在二叉搜索樹中中序遍歷的結(jié)果是一個升序序列。所謂中序后繼就是中序遍歷序列中位于節(jié)點 $p$ 之后的下一個節(jié)點——即值上剛剛比 $p$ 大的那個節(jié)點。本題難度為中等Medium標簽為樹、深度優(yōu)先搜索收錄于 lcci程序員面試金典題集中題目編號為 04.06。示例分析示例 1輸入root [2,1,3], p 12 / \ 1 3輸出2分析對樹[2,1,3]做中序遍歷得到[1, 2, 3]節(jié)點1的下一個節(jié)點是2。示例 2輸入root [5,3,6,2,4,null,null,1], p 65 / \ 3 6 / \ 2 4 / 1輸出null分析中序遍歷序列為[1, 2, 3, 4, 5, 6]節(jié)點6已經(jīng)是中序序列的最后一個節(jié)點不存在后繼因此返回null。題目完整描述見 README_EN.md 與 README.md。思路一樸素中序遍歷O(n)最直接的想法是對整棵 BST 做一次完整的中序遍歷在遍歷過程中記錄上一個訪問的節(jié)點當(dāng)上一個節(jié)點等于p時當(dāng)前訪問節(jié)點即為中序后繼。def inorder_successor_naive(root, p): stack [] prev None cur root while stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() if prev is p: return cur prev cur cur cur.right return None這種做法的正確性依賴 BST 中序遍歷的升序性質(zhì)但其時間與空間復(fù)雜度均為 $O(n)$$n$ 為節(jié)點總數(shù)。它沒有利用 BST 的有序性對于高度為 $h$、節(jié)點總數(shù)為 $n$ 的樹而言屬于線性開銷。思路二利用 BST 有序性的二分查找O(h)原題解的核心思路在于中序后繼是所有大于 $p.val$ 的節(jié)點中值最小的那一個。這一觀察將問題從遍歷整棵樹轉(zhuǎn)化為沿路徑定向搜索從而可以在 $O(h)$ 時間內(nèi)完成且空間復(fù)雜度為 $O(1)$完全不需要父指針也不需要 Morris 線索遍歷。后繼節(jié)點的兩條判定條件中序后繼節(jié)點的值大于$p$ 的節(jié)點值中序后繼是所有大于 $p$ 的節(jié)點中值最小的節(jié)點。搜索規(guī)則從根節(jié)點root出發(fā)維護一個候選答案ans循環(huán)執(zhí)行若root.val p.val則root是 $p$ 的潛在中序后繼將其記為ans然后轉(zhuǎn)向左子樹繼續(xù)尋找更小的更大值即root root.left若root.val p.val則root及其左子樹都不可能成為后繼值不夠大后繼只可能存在于右子樹即root root.right。循環(huán)終止后ans即為所求。若整個過程中從未出現(xiàn)root.val p.val的節(jié)點例如 $p$ 是整棵樹中值最大的節(jié)點ans保持null正好對應(yīng)沒有后繼的語義。倉庫中的多語言實現(xiàn)doocs/leetcode 倉庫在 lcci/04.06.Successor 目錄下提供了 Python、Java、C、Go、TypeScript、JavaScript、Swift 七種語言的獨立實現(xiàn)文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.swift算法邏輯完全一致只是語言語法不同。Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def inorderSuccessor(self, root: TreeNode, p: TreeNode) - Optional[TreeNode]: ans None while root: if root.val p.val: ans root root root.left else: root root.right return ansJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { TreeNode ans null; while (root ! null) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { TreeNode* ans nullptr; while (root) { if (root-val p-val) { ans root; root root-left; } else { root root-right; } } return ans; } };Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) { for root ! nil { if root.Val p.Val { ans root root root.Left } else { root root.Right } } return }TypeScript/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function inorderSuccessor(root: TreeNode | null, p: TreeNode | null): TreeNode | null { let ans: TreeNode | null null; while (root) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; }JavaScript/** * Definition for a binary tree node. * function TreeNode(val) { * this.val val; * this.left this.right null; * } */ /** * param {TreeNode} root * param {TreeNode} p * return {TreeNode} */ var inorderSuccessor function (root, p) { let ans null; while (root) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; };Swift/* class TreeNode { * var val: Int * var left: TreeNode? * var right: TreeNode? * * init(_ val: Int) { * self.val val * self.left nil * self.right nil * } * } */ class Solution { func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode?) - TreeNode? { var current root var successor: TreeNode? nil while let node current { if node.val p!.val { successor node current node.left } else { current node.right } } return successor } }各實現(xiàn)文件可在 lcci/04.06.Successor/Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.swift 中查看完整源碼。所有實現(xiàn)均與 README_EN.md 內(nèi)嵌的題解代碼一一對應(yīng)可直接復(fù)制運行。算法正確性剖析該算法為什么是對的關(guān)鍵在于維護的候選答案ans始終是到目前為止遇到的所有大于p.val的節(jié)點中值最小的那個當(dāng)root.val p.val時root是一個合法候選但它的左子樹中可能存在更小但仍大于p.val的節(jié)點因此更新ans root后繼續(xù)下探左子樹當(dāng)root.val p.val時root及其整棵左子樹的值都不大于p.val可以全部剪枝只搜索右子樹從根到葉子的每一條路徑最多訪問 $h$ 個節(jié)點其中 $h$ 是樹的高度最終停在葉子的空子樹上循環(huán)自然結(jié)束。以示例 2 為例p 6值為 6 的節(jié)點是全局最大值從根 5 開始5 6不成立轉(zhuǎn)向右子樹 66 6不成立轉(zhuǎn)向右子樹空循環(huán)結(jié)束ans始終為null正確返回null。復(fù)雜度與擴展討論時間復(fù)雜度$O(h)$其中 $h$ 為二叉搜索樹的高度。在理想平衡樹中 $h O(\log n)$在退化鏈狀樹中 $h O(n)$。空間復(fù)雜度$O(1)$僅使用常數(shù)個指針變量ans與root優(yōu)于需要顯式?；蜻f歸棧的中序遍歷方案。延伸思考如果題目給出的是父指針版本如 LeetCode 的Node定義包含parent同樣可以在 $O(h)$ 時間內(nèi)通過有右子樹則取右子樹最左節(jié)點否則向上找第一個作為左孩子的祖先完成本題的對稱問題中序前驅(qū)predecessor可用完全對稱的規(guī)則求解當(dāng)root.val p.val時記錄候選并轉(zhuǎn)向右子樹否則轉(zhuǎn)向左子樹該二分查找思路同樣適用于題目 面試題 04.06 收錄頁所標注的樹、深度優(yōu)先搜索兩類考點可遷移到其他在有序結(jié)構(gòu)中定位相鄰元素的問題上?？偨Y(jié)面試題 04.06 的核心考點在于發(fā)現(xiàn)并利用 BST 中序遍歷的升序有序性中序后繼 大于p的最小節(jié)點。據(jù)此可以在 $O(h)$ 時間、$O(1)$ 空間內(nèi)完成查找代碼僅需一個while循環(huán)與一個候選指針變量是典型的用數(shù)學(xué)觀察簡化實現(xiàn)的面試題。完整題解與七種語言實現(xiàn)均可在 lcci/04.06.Successor 目錄下查閱。贊分享示例工程教程【免費下載鏈接】leetcodeLeetCode solutions in any programming language | 多種編程語言實現(xiàn) LeetCode、《劍指 Offer第 2 版》、《程序員面試金典第 6 版》題解項目地址https://gitcode.com/doocs/leetcode點擊查看免費下載相關(guān)推薦劍指 Offer 04.06 后繼者Successor LCCI二叉搜索樹中序后繼的二分搜索解法全解劍指 Offer 04.06 后繼者Successor LCCI二叉搜索樹中序后繼的二分搜索解法全解 本文圍繞《程序員面試金典第 6 版》中的面試題示例工程教程二叉搜索樹中序后繼節(jié)點算法解析二叉搜索樹中序后繼節(jié)點算法解析 問題描述 在二叉搜索樹 BST 中給定一個節(jié)點我們需要找到它的中序遍歷順序下的后繼節(jié)點。中序遍歷順序是指按照左子樹 根節(jié)點示例工程教程doocs/leetcode 題解精講面試題 04.09 二叉搜索樹序列BST Sequences——遞歸交織子序列算法詳解doocs/leetcode 題解精講面試題 04.09 二叉搜索樹序列BST Sequences——遞歸交織子序列算法詳解 本篇技術(shù)指南圍繞 doocs示例工程教程上一篇高性能Windows系統(tǒng)優(yōu)化工具架構(gòu)解析與深度清理技術(shù)實現(xiàn)下一篇Zotero中文文獻管理終極方案Jasminum元數(shù)據(jù)自動抓取完整指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 面試題 04.06 后繼者：二叉搜索樹中序后繼的二分查找算法詳解（doocs/leetcode 題解）
示例工程教程【免費下載鏈接】leetcodeLeetCode solutions in any programming language | 多種編程語言實現(xiàn) LeetCode、《劍指 Offer第 2 版》、《程序員面試金典第 6 版》題解項目地址https://gitcode.com/doocs/leetcode點擊查看免費下載本文以 doocs/leetcode 倉庫中《程序員面試金典》系列題目 04.06. Successor后繼者 的官方題解為骨架系統(tǒng)講解二叉搜索樹BST中序后繼節(jié)點的定義、樸素遍歷解法與 O(h) 二分查找解法并基于倉庫中的多語言實現(xiàn)給出可直接運行的代碼與復(fù)雜度分析幫助你掌握面試中高頻的 BST 有序性利用技巧。題目概述什么是中序后繼題目要求設(shè)計一個算法找出二叉搜索樹中指定節(jié)點的下一個節(jié)點即中序后繼。如果指定節(jié)點沒有對應(yīng)的下一個節(jié)點則返回null。在二叉搜索樹中中序遍歷的結(jié)果是一個升序序列。所謂中序后繼就是中序遍歷序列中位于節(jié)點 $p$ 之后的下一個節(jié)點——即值上剛剛比 $p$ 大的那個節(jié)點。本題難度為中等Medium標簽為樹、深度優(yōu)先搜索收錄于 lcci程序員面試金典題集中題目編號為 04.06。示例分析示例 1輸入root [2,1,3], p 12 / \ 1 3輸出2分析對樹[2,1,3]做中序遍歷得到[1, 2, 3]節(jié)點1的下一個節(jié)點是2。示例 2輸入root [5,3,6,2,4,null,null,1], p 65 / \ 3 6 / \ 2 4 / 1輸出null分析中序遍歷序列為[1, 2, 3, 4, 5, 6]節(jié)點6已經(jīng)是中序序列的最后一個節(jié)點不存在后繼因此返回null。題目完整描述見 README_EN.md 與 README.md。思路一樸素中序遍歷O(n)最直接的想法是對整棵 BST 做一次完整的中序遍歷在遍歷過程中記錄上一個訪問的節(jié)點當(dāng)上一個節(jié)點等于p時當(dāng)前訪問節(jié)點即為中序后繼。def inorder_successor_naive(root, p): stack [] prev None cur root while stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() if prev is p: return cur prev cur cur cur.right return None這種做法的正確性依賴 BST 中序遍歷的升序性質(zhì)但其時間與空間復(fù)雜度均為 $O(n)$$n$ 為節(jié)點總數(shù)。它沒有利用 BST 的有序性對于高度為 $h$、節(jié)點總數(shù)為 $n$ 的樹而言屬于線性開銷。思路二利用 BST 有序性的二分查找O(h)原題解的核心思路在于中序后繼是所有大于 $p.val$ 的節(jié)點中值最小的那一個。這一觀察將問題從遍歷整棵樹轉(zhuǎn)化為沿路徑定向搜索從而可以在 $O(h)$ 時間內(nèi)完成且空間復(fù)雜度為 $O(1)$完全不需要父指針也不需要 Morris 線索遍歷。后繼節(jié)點的兩條判定條件中序后繼節(jié)點的值大于$p$ 的節(jié)點值中序后繼是所有大于 $p$ 的節(jié)點中值最小的節(jié)點。搜索規(guī)則從根節(jié)點root出發(fā)維護一個候選答案ans循環(huán)執(zhí)行若root.val p.val則root是 $p$ 的潛在中序后繼將其記為ans然后轉(zhuǎn)向左子樹繼續(xù)尋找更小的更大值即root root.left若root.val p.val則root及其左子樹都不可能成為后繼值不夠大后繼只可能存在于右子樹即root root.right。循環(huán)終止后ans即為所求。若整個過程中從未出現(xiàn)root.val p.val的節(jié)點例如 $p$ 是整棵樹中值最大的節(jié)點ans保持null正好對應(yīng)沒有后繼的語義。倉庫中的多語言實現(xiàn)doocs/leetcode 倉庫在 lcci/04.06.Successor 目錄下提供了 Python、Java、C、Go、TypeScript、JavaScript、Swift 七種語言的獨立實現(xiàn)文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.swift算法邏輯完全一致只是語言語法不同。Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def inorderSuccessor(self, root: TreeNode, p: TreeNode) - Optional[TreeNode]: ans None while root: if root.val p.val: ans root root root.left else: root root.right return ansJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { TreeNode ans null; while (root ! null) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { TreeNode* ans nullptr; while (root) { if (root-val p-val) { ans root; root root-left; } else { root root-right; } } return ans; } };Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func inorderSuccessor(root *TreeNode, p *TreeNode) (ans *TreeNode) { for root ! nil { if root.Val p.Val { ans root root root.Left } else { root root.Right } } return }TypeScript/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function inorderSuccessor(root: TreeNode | null, p: TreeNode | null): TreeNode | null { let ans: TreeNode | null null; while (root) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; }JavaScript/** * Definition for a binary tree node. * function TreeNode(val) { * this.val val; * this.left this.right null; * } */ /** * param {TreeNode} root * param {TreeNode} p * return {TreeNode} */ var inorderSuccessor function (root, p) { let ans null; while (root) { if (root.val p.val) { ans root; root root.left; } else { root root.right; } } return ans; };Swift/* class TreeNode { * var val: Int * var left: TreeNode? * var right: TreeNode? * * init(_ val: Int) { * self.val val * self.left nil * self.right nil * } * } */ class Solution { func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode?) - TreeNode? { var current root var successor: TreeNode? nil while let node current { if node.val p!.val { successor node current node.left } else { current node.right } } return successor } }各實現(xiàn)文件可在 lcci/04.06.Successor/Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.swift 中查看完整源碼。所有實現(xiàn)均與 README_EN.md 內(nèi)嵌的題解代碼一一對應(yīng)可直接復(fù)制運行。算法正確性剖析該算法為什么是對的關(guān)鍵在于維護的候選答案ans始終是到目前為止遇到的所有大于p.val的節(jié)點中值最小的那個當(dāng)root.val p.val時root是一個合法候選但它的左子樹中可能存在更小但仍大于p.val的節(jié)點因此更新ans root后繼續(xù)下探左子樹當(dāng)root.val p.val時root及其整棵左子樹的值都不大于p.val可以全部剪枝只搜索右子樹從根到葉子的每一條路徑最多訪問 $h$ 個節(jié)點其中 $h$ 是樹的高度最終停在葉子的空子樹上循環(huán)自然結(jié)束。以示例 2 為例p 6值為 6 的節(jié)點是全局最大值從根 5 開始5 6不成立轉(zhuǎn)向右子樹 66 6不成立轉(zhuǎn)向右子樹空循環(huán)結(jié)束ans始終為null正確返回null。復(fù)雜度與擴展討論時間復(fù)雜度$O(h)$其中 $h$ 為二叉搜索樹的高度。在理想平衡樹中 $h O(\log n)$在退化鏈狀樹中 $h O(n)$。空間復(fù)雜度$O(1)$僅使用常數(shù)個指針變量ans與root優(yōu)于需要顯式?；蜻f歸棧的中序遍歷方案。延伸思考如果題目給出的是父指針版本如 LeetCode 的Node定義包含parent同樣可以在 $O(h)$ 時間內(nèi)通過有右子樹則取右子樹最左節(jié)點否則向上找第一個作為左孩子的祖先完成本題的對稱問題中序前驅(qū)predecessor可用完全對稱的規(guī)則求解當(dāng)root.val p.val時記錄候選并轉(zhuǎn)向右子樹否則轉(zhuǎn)向左子樹該二分查找思路同樣適用于題目 面試題 04.06 收錄頁所標注的樹、深度優(yōu)先搜索兩類考點可遷移到其他在有序結(jié)構(gòu)中定位相鄰元素的問題上?？偨Y(jié)面試題 04.06 的核心考點在于發(fā)現(xiàn)并利用 BST 中序遍歷的升序有序性中序后繼 大于p的最小節(jié)點。據(jù)此可以在 $O(h)$ 時間、$O(1)$ 空間內(nèi)完成查找代碼僅需一個while循環(huán)與一個候選指針變量是典型的用數(shù)學(xué)觀察簡化實現(xiàn)的面試題。完整題解與七種語言實現(xiàn)均可在 lcci/04.06.Successor 目錄下查閱。贊分享示例工程教程【免費下載鏈接】leetcodeLeetCode solutions in any programming language | 多種編程語言實現(xiàn) LeetCode、《劍指 Offer第 2 版》、《程序員面試金典第 6 版》題解項目地址https://gitcode.com/doocs/leetcode點擊查看免費下載相關(guān)推薦劍指 Offer 04.06 后繼者Successor LCCI二叉搜索樹中序后繼的二分搜索解法全解劍指 Offer 04.06 后繼者Successor LCCI二叉搜索樹中序后繼的二分搜索解法全解 本文圍繞《程序員面試金典第 6 版》中的面試題示例工程教程二叉搜索樹中序后繼節(jié)點算法解析二叉搜索樹中序后繼節(jié)點算法解析 問題描述 在二叉搜索樹 BST 中給定一個節(jié)點我們需要找到它的中序遍歷順序下的后繼節(jié)點。中序遍歷順序是指按照左子樹 根節(jié)點示例工程教程doocs/leetcode 題解精講面試題 04.09 二叉搜索樹序列BST Sequences——遞歸交織子序列算法詳解doocs/leetcode 題解精講面試題 04.09 二叉搜索樹序列BST Sequences——遞歸交織子序列算法詳解 本篇技術(shù)指南圍繞 doocs示例工程教程上一篇高性能Windows系統(tǒng)優(yōu)化工具架構(gòu)解析與深度清理技術(shù)實現(xiàn)下一篇Zotero中文文獻管理終極方案Jasminum元數(shù)據(jù)自動抓取完整指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考