二叉树边界遍历Boundary of Binary Tree题解三步拆分法与单次前序遍历法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读二叉树的边界Boundary是指沿着树的外轮廓从根节点出发逆时针绕树一圈所经过的全部节点它由左边界自上而下不含叶子、全部叶子节点自左而右、右边界自下而上不含叶子三部分组成。本篇文章基于仓库文档 articles/boundary-of-binary-tree.md 展开系统讲解两种主流解法分三部分独立收集的简单方案与单次前序遍历 标志位分类方案。读完本文你将掌握边界节点的判定规则、右边界逆序输出的处理技巧以及如何用一次 DFS 完成全部收集并能规避叶子节点重复、右边界顺序颠倒、单子节点漏收集三类高频陷阱。前置知识在动手实现之前需要先具备以下基础二叉树遍历Binary Tree Traversal——理解前序preorder、中序inorder、后序postorder三种遍历模式的访问顺序。仓库中 articles/binary-tree-preorder-traversal.md、articles/binary-tree-inorder-traversal.md、articles/binary-tree-postorder-traversal.md 分别对这三种遍历做了专门讲解可作为对照参考。递归Recursion——使用递归函数遍历树结构并收集节点这是收集叶子节点与执行前序遍历的基础。栈Stack Data Structure——利用栈的后进先出特性反转元素顺序右边界bottom-to-top的逆序输出正是借助栈完成的。问题定义什么是二叉树的边界给定一棵二叉树的根节点root按逆时针方向返回树的边界节点值列表。边界由三部分拼接而成左边界Left Boundary从根节点的左孩子出发沿left优先、缺失时沿right下行排除叶子节点顺序为自上而下叶子节点Leaves整棵树的所有叶子按从左到右的顺序收集右边界Right Boundary从根节点的右孩子出发沿right优先、缺失时沿left下行排除叶子节点输出顺序为自下而上。根节点单独处理若根不是叶子则作为结果的第一个元素输出。解法一简单方案分三部分收集直觉既然边界天然可以拆成左边界 叶子 右边界三段最直观的做法就是分别处理每一段沿着左边缘一路下行收集左边界通过递归收集所有叶子沿着右边缘下行时把节点压入栈中最后统一弹出实现逆序从而得到自下而上的右边界。算法步骤若根节点为null直接返回空列表若根节点不是叶子先把根的值加入结果遍历左边界从root.left出发始终优先走向左孩子左孩子为空时走向右孩子只收集非叶子节点用递归辅助函数收集所有叶子节点保证从左到右的顺序遍历右边界从root.right出发始终优先走向右孩子右孩子为空时走向左孩子把非叶子节点压入栈依次弹出栈中元素加入结果完成逆序返回结果。多语言实现:::tabs-startclass Solution: def isLeaf(self, t: Optional[TreeNode]) - bool: return t.left is None and t.right is None def addLeaves(self, res: List[int], root: Optional[TreeNode]) - None: if self.isLeaf(root): res.append(root.val) else: if root.left is not None: self.addLeaves(res, root.left) if root.right is not None: self.addLeaves(res, root.right) def boundaryOfBinaryTree(self, root: Optional[TreeNode]) - List[int]: res [] if root is None: return res if not self.isLeaf(root): res.append(root.val) t root.left while t is not None: if not self.isLeaf(t): res.append(t.val) if t.left is not None: t t.left else: t t.right self.addLeaves(res, root) stack [] t root.right while t is not None: if not self.isLeaf(t): stack.append(t.val) if t.right is not None: t t.right else: t t.left while stack: res.append(stack.pop()) return resclass Solution { public boolean isLeaf(TreeNode t) { return t.left null t.right null; } public void addLeaves(ListInteger res, TreeNode root) { if (isLeaf(root)) { res.add(root.val); } else { if (root.left ! null) { addLeaves(res, root.left); } if (root.right ! null) { addLeaves(res, root.right); } } } public ListInteger boundaryOfBinaryTree(TreeNode root) { ArrayListInteger res new ArrayList(); if (root null) { return res; } if (!isLeaf(root)) { res.add(root.val); } TreeNode t root.left; while (t ! null) { if (!isLeaf(t)) { res.add(t.val); } if (t.left ! null) { t t.left; } else { t t.right; } } addLeaves(res, root); StackInteger s new Stack(); t root.right; while (t ! null) { if (!isLeaf(t)) { s.push(t.val); } if (t.right ! null) { t t.right; } else { t t.left; } } while (!s.empty()) { res.add(s.pop()); } return res; } }class Solution { public: bool isLeaf(TreeNode* t) { return t-left nullptr t-right nullptr; } void addLeaves(vectorint res, TreeNode* root) { if (isLeaf(root)) { res.push_back(root-val); } else { if (root-left ! nullptr) { addLeaves(res, root-left); } if (root-right ! nullptr) { addLeaves(res, root-right); } } } vectorint boundaryOfBinaryTree(TreeNode* root) { vectorint res; if (root nullptr) { return res; } if (!isLeaf(root)) { res.push_back(root-val); } TreeNode* t root-left; while (t ! nullptr) { if (!isLeaf(t)) { res.push_back(t-val); } if (t-left ! nullptr) { t t-left; } else { t t-right; } } addLeaves(res, root); stackint s; t root-right; while (t ! nullptr) { if (!isLeaf(t)) { s.push(t-val); } if (t-right ! nullptr) { t t-right; } else { t t-left; } } while (!s.empty()) { res.push_back(s.top()); s.pop(); } return res; } };class Solution { /** * param {TreeNode} root * return {number[]} */ isLeaf(t) { return t.left null t.right null; } addLeaves(res, root) { if (this.isLeaf(root)) { res.push(root.val); } else { if (root.left ! null) { this.addLeaves(res, root.left); } if (root.right ! null) { this.addLeaves(res, root.right); } } } boundaryOfBinaryTree(root) { const res []; if (root null) { return res; } if (!this.isLeaf(root)) { res.push(root.val); } let t root.left; while (t ! null) { if (!this.isLeaf(t)) { res.push(t.val); } if (t.left ! null) { t t.left; } else { t t.right; } } this.addLeaves(res, root); const stack []; t root.right; while (t ! null) { if (!this.isLeaf(t)) { stack.push(t.val); } if (t.right ! null) { t t.right; } else { t t.left; } } while (stack.length 0) { res.push(stack.pop()); } return res; } }func isLeaf(t *TreeNode) bool { return t.Left nil t.Right nil } func addLeaves(res *[]int, root *TreeNode) { if isLeaf(root) { *res append(*res, root.Val) } else { if root.Left ! nil { addLeaves(res, root.Left) } if root.Right ! nil { addLeaves(res, root.Right) } } } func boundaryOfBinaryTree(root *TreeNode) []int { res : []int{} if root nil { return res } if !isLeaf(root) { res append(res, root.Val) } t : root.Left for t ! nil { if !isLeaf(t) { res append(res, t.Val) } if t.Left ! nil { t t.Left } else { t t.Right } } addLeaves(res, root) stack : []int{} t root.Right for t ! nil { if !isLeaf(t) { stack append(stack, t.Val) } if t.Right ! nil { t t.Right } else { t t.Left } } for len(stack) 0 { res append(res, stack[len(stack)-1]) stack stack[:len(stack)-1] } return res }class Solution { private fun isLeaf(t: TreeNode): Boolean { return t.left null t.right null } private fun addLeaves(res: MutableListInt, root: TreeNode) { if (isLeaf(root)) { res.add(root.val) } else { root.left?.let { addLeaves(res, it) } root.right?.let { addLeaves(res, it) } } } fun boundaryOfBinaryTree(root: TreeNode?): ListInt { val res mutableListOfInt() if (root null) return res if (!isLeaf(root)) { res.add(root.val) } var t root.left while (t ! null) { if (!isLeaf(t)) { res.add(t.val) } t if (t.left ! null) t.left else t.right } addLeaves(res, root) val stack mutableListOfInt() t root.right while (t ! null) { if (!isLeaf(t)) { stack.add(t.val) } t if (t.right ! null) t.right else t.left } while (stack.isNotEmpty()) { res.add(stack.removeAt(stack.size - 1)) } return res } }class Solution { func isLeaf(_ t: TreeNode) - Bool { return t.left nil t.right nil } func addLeaves(_ res: inout [Int], _ root: TreeNode) { if isLeaf(root) { res.append(root.val) } else { if let left root.left { addLeaves(res, left) } if let right root.right { addLeaves(res, right) } } } func boundaryOfBinaryTree(_ root: TreeNode?) - [Int] { var res [Int]() guard let root root else { return res } if !isLeaf(root) { res.append(root.val) } var t root.left while t ! nil { if !isLeaf(t!) { res.append(t!.val) } t t!.left ! nil ? t!.left : t!.right } addLeaves(res, root) var stack [Int]() t root.right while t ! nil { if !isLeaf(t!) { stack.append(t!.val) } t t!.right ! nil ? t!.right : t!.left } while !stack.isEmpty { res.append(stack.removeLast()) } return res } }impl Solution { pub fn boundary_of_binary_tree(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let root match root { Some(r) r, None return res, }; if !Self::is_leaf(root) { res.push(root.borrow().val); } // Left boundary let mut t root.borrow().left.clone(); while let Some(node) t { if !Self::is_leaf(node) { res.push(node.borrow().val); } let next if node.borrow().left.is_some() { node.borrow().left.clone() } else { node.borrow().right.clone() }; t next; } // Leaves Self::add_leaves(root, mut res); // Right boundary (reversed) let mut stack Vec::new(); t root.borrow().right.clone(); while let Some(node) t { if !Self::is_leaf(node) { stack.push(node.borrow().val); } let next if node.borrow().right.is_some() { node.borrow().right.clone() } else { node.borrow().left.clone() }; t next; } while let Some(val) stack.pop() { res.push(val); } res } fn is_leaf(node: RcRefCellTreeNode) - bool { let n node.borrow(); n.left.is_none() n.right.is_none() } fn add_leaves(node: RcRefCellTreeNode, res: mut Veci32) { if Self::is_leaf(node) { res.push(node.borrow().val); } else { if let Some(ref left) node.borrow().left { Self::add_leaves(left, res); } if let Some(ref right) node.borrow().right { Self::add_leaves(right, res); } } } }::tabs-end复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$其中 $n$ 为树中节点的个数。时间上左边界、右边界、叶子三部分恰好遍历整棵树各节点一次空间上最坏情况链状树下递归深度与栈大小均为 $O(n)$。解法二单次前序遍历 标志位分类直觉简单方案需要三段独立的遍历而边界收集其实可以在一次前序遍历中完成遍历时给每个节点打上一个角色标志据此决定把它放进哪一类容器。标志共四种根节点0、左边界1、右边界2、内部节点3。左边界节点直接按序追加到left_boundary右边界节点逆序收集到right_boundary通过头部插入实现叶子单独收集到leaves最后拼接left_boundary leaves right_boundary即可。标志位传播规则遍历到每个节点时需要依据当前节点的标志与子节点的存在情况为其左右孩子计算新的标志孩子当前标志兄弟节点情况孩子标志含义左孩子0根或1左边界任意1继承左边界身份左孩子2右边界cur.right null无右兄弟2右边界上的独子仍属右边界左孩子其他其他3内部节点右孩子0根或2右边界任意2继承右边界身份右孩子1左边界cur.left null无左兄弟1左边界上的独子仍属左边界右孩子其他其他3内部节点核心思想左边界节点沿外轮廓下行时若唯一的孩子在右侧则这个独子依然贴着边界必须继承边界身份右边界同理。这保证了一棵退化链状树的边界依然能被完整收集。算法步骤创建三个列表left_boundary、right_boundary、leaves从根节点标志0开始执行前序遍历若节点属于右边界标志2将其值头部插入right_boundary等效于收集后逆序若节点属于左边界或根标志0或1将其值追加到left_boundary若节点是叶子且未被计入边界追加到leaves对每个孩子按上表规则计算其标志后递归最后拼接left_boundary leaves right_boundary并返回。多语言实现:::tabs-startclass Solution: def boundaryOfBinaryTree(self, root: Optional[TreeNode]) - List[int]: left_boundary, right_boundary, leaves [], [], [] self.preorder(root, left_boundary, right_boundary, leaves, 0) left_boundary.extend(leaves) left_boundary.extend(right_boundary) return left_boundary def is_leaf(self, cur): return cur.left is None and cur.right is None def is_right_boundary(self, flag): return flag 2 def is_left_boundary(self, flag): return flag 1 def is_root(self, flag): return flag 0 def left_child_flag(self, cur, flag): if self.is_left_boundary(flag) or self.is_root(flag): return 1 elif self.is_right_boundary(flag) and cur.right is None: return 2 else: return 3 def right_child_flag(self, cur, flag): if self.is_right_boundary(flag) or self.is_root(flag): return 2 elif self.is_left_boundary(flag) and cur.left is None: return 1 else: return 3 def preorder(self, cur, left_boundary, right_boundary, leaves, flag): if cur is None: return if self.is_right_boundary(flag): right_boundary.insert(0, cur.val) elif self.is_left_boundary(flag) or self.is_root(flag): left_boundary.append(cur.val) elif self.is_leaf(cur): leaves.append(cur.val) self.preorder(cur.left, left_boundary, right_boundary, leaves, self.left_child_flag(cur, flag)) self.preorder(cur.right, left_boundary, right_boundary, leaves, self.right_child_flag(cur, flag))class Solution { public List Integer boundaryOfBinaryTree(TreeNode root) { List Integer left_boundary new LinkedList (), right_boundary new LinkedList (), leaves new LinkedList (); preorder(root, left_boundary, right_boundary, leaves, 0); left_boundary.addAll(leaves); left_boundary.addAll(right_boundary); return left_boundary; } public boolean isLeaf(TreeNode cur) { return (cur.left null cur.right null); } public boolean isRightBoundary(int flag) { return (flag 2); } public boolean isLeftBoundary(int flag) { return (flag 1); } public boolean isRoot(int flag) { return (flag 0); } public int leftChildFlag(TreeNode cur, int flag) { if (isLeftBoundary(flag) || isRoot(flag)) return 1; else if (isRightBoundary(flag) cur.right null) return 2; else return 3; } public int rightChildFlag(TreeNode cur, int flag) { if (isRightBoundary(flag) || isRoot(flag)) return 2; else if (isLeftBoundary(flag) cur.left null) return 1; else return 3; } public void preorder(TreeNode cur, List Integer left_boundary, List Integer right_boundary, List Integer leaves, int flag) { if (cur null) return; if (isRightBoundary(flag)) right_boundary.add(0, cur.val); else if (isLeftBoundary(flag) || isRoot(flag)) left_boundary.add(cur.val); else if (isLeaf(cur)) leaves.add(cur.val); preorder(cur.left, left_boundary, right_boundary, leaves, leftChildFlag(cur, flag)); preorder(cur.right, left_boundary, right_boundary, leaves, rightChildFlag(cur, flag)); } }class Solution { public: vectorint boundaryOfBinaryTree(TreeNode* root) { vectorint left_boundary, right_boundary, leaves; preorder(root, left_boundary, right_boundary, leaves, 0); left_boundary.insert(left_boundary.end(), leaves.begin(), leaves.end()); left_boundary.insert(left_boundary.end(), right_boundary.begin(), right_boundary.end()); return left_boundary; } private: bool isLeaf(TreeNode* cur) { return cur-left nullptr cur-right nullptr; } bool isRightBoundary(int flag) { return flag 2; } bool isLeftBoundary(int flag) { return flag 1; } bool isRoot(int flag) { return flag 0; } int leftChildFlag(TreeNode* cur, int flag) { if (isLeftBoundary(flag) || isRoot(flag)) { return 1; } else if (isRightBoundary(flag) cur-right nullptr) { return 2; } else { return 3; } } int rightChildFlag(TreeNode* cur, int flag) { if (isRightBoundary(flag) || isRoot(flag)) { return 2; } else if (isLeftBoundary(flag) cur-left nullptr) { return 1; } else { return 3; } } void preorder(TreeNode* cur, vectorint left_boundary, vectorint right_boundary, vectorint leaves, int flag) { if (cur nullptr) { return; } if (isRightBoundary(flag)) { right_boundary.insert(right_boundary.begin(), cur-val); } else if (isLeftBoundary(flag) || isRoot(flag)) { left_boundary.push_back(cur-val); } else if (isLeaf(cur)) { leaves.push_back(cur-val); } preorder(cur-left, left_boundary, right_boundary, leaves, leftChildFlag(cur, flag)); preorder(cur-right, left_boundary, right_boundary, leaves, rightChildFlag(cur, flag)); } };class Solution { /** * param {TreeNode} root * return {number[]} */ boundaryOfBinaryTree(root) { const left_boundary [], right_boundary [], leaves []; this.preorder(root, left_boundary, right_boundary, leaves, 0); left_boundary.push(...leaves); left_boundary.push(...right_boundary); return left_boundary; } isLeaf(cur) { return cur.left null cur.right null; } isRightBoundary(flag) { return flag 2; } isLeftBoundary(flag) { return flag 1; } isRoot(flag) { return flag 0; } leftChildFlag(cur, flag) { if (this.isLeftBoundary(flag) || this.isRoot(flag)) { return 1; } else if (this.isRightBoundary(flag) cur.right null) { return 2; } else { return 3; } } rightChildFlag(cur, flag) { if (this.isRightBoundary(flag) || this.isRoot(flag)) { return 2; } else if (this.isLeftBoundary(flag) cur.left null) { return 1; } else { return 3; } } preorder(cur, left_boundary, right_boundary, leaves, flag) { if (cur null) { return; } if (this.isRightBoundary(flag)) { right_boundary.unshift(cur.val); } else if (this.isLeftBoundary(flag) || this.isRoot(flag)) { left_boundary.push(cur.val); } else if (this.isLeaf(cur)) { leaves.push(cur.val); } this.preorder( cur.left, left_boundary, right_boundary, leaves, this.leftChildFlag(cur, flag), ); this.preorder( cur.right, left_boundary, right_boundary, leaves, this.rightChildFlag(cur, flag), ); } }func boundaryOfBinaryTree(root *TreeNode) []int { leftBoundary : []int{} rightBoundary : []int{} leaves : []int{} var preorder func(cur *TreeNode, flag int) preorder func(cur *TreeNode, flag int) { if cur nil { return } isLeaf : cur.Left nil cur.Right nil if flag 2 { rightBoundary append([]int{cur.Val}, rightBoundary...) } else if flag 1 || flag 0 { leftBoundary append(leftBoundary, cur.Val) } else if isLeaf { leaves append(leaves, cur.Val) } leftFlag : 3 if flag 1 || flag 0 { leftFlag 1 } else if flag 2 cur.Right nil { leftFlag 2 } rightFlag : 3 if flag 2 || flag 0 { rightFlag 2 } else if flag 1 cur.Left nil { rightFlag 1 } preorder(cur.Left, leftFlag) preorder(cur.Right, rightFlag) } preorder(root, 0) leftBoundary append(leftBoundary, leaves...) leftBoundary append(leftBoundary, rightBoundary...) return leftBoundary }class Solution { fun boundaryOfBinaryTree(root: TreeNode?): ListInt { val leftBoundary mutableListOfInt() val rightBoundary mutableListOfInt() val leaves mutableListOfInt() fun isLeaf(cur: TreeNode) cur.left null cur.right null fun leftChildFlag(cur: TreeNode, flag: Int): Int { return when { flag 1 || flag 0 - 1 flag 2 cur.right null - 2 else - 3 } } fun rightChildFlag(cur: TreeNode, flag: Int): Int { return when { flag 2 || flag 0 - 2 flag 1 cur.left null - 1 else - 3 } } fun preorder(cur: TreeNode?, flag: Int) { if (cur null) return when { flag 2 - rightBoundary.add(0, cur.val) flag 1 || flag 0 - leftBoundary.add(cur.val) isLeaf(cur) - leaves.add(cur.val) } preorder(cur.left, leftChildFlag(cur, flag)) preorder(cur.right, rightChildFlag(cur, flag)) } preorder(root, 0) leftBoundary.addAll(leaves) leftBoundary.addAll(rightBoundary) return leftBoundary } }class Solution { func boundaryOfBinaryTree(_ root: TreeNode?) - [Int] { var leftBoundary [Int]() var rightBoundary [Int]() var leaves [Int]() func isLeaf(_ cur: TreeNode) - Bool { return cur.left nil cur.right nil } func leftChildFlag(_ cur: TreeNode, _ flag: Int) - Int { if flag 1 || flag 0 { return 1 } else if flag 2 cur.right nil { return 2 } return 3 } func rightChildFlag(_ cur: TreeNode, _ flag: Int) - Int { if flag 2 || flag 0 { return 2 } else if flag 1 cur.left nil { return 1 } return 3 } func preorder(_ cur: TreeNode?, _ flag: Int) { guard let cur cur else { return } if flag 2 { rightBoundary.insert(cur.val, at: 0) } else if flag 1 || flag 0 { leftBoundary.append(cur.val) } else if isLeaf(cur) { leaves.append(cur.val) } preorder(cur.left, leftChildFlag(cur, flag)) preorder(cur.right, rightChildFlag(cur, flag)) } preorder(root, 0) leftBoundary.append(contentsOf: leaves) leftBoundary.append(contentsOf: rightBoundary) return leftBoundary } }impl Solution { pub fn boundary_of_binary_tree(root: OptionRcRefCellTreeNode) - Veci32 { let mut left_boundary Vec::new(); let mut right_boundary Vec::new(); let mut leaves Vec::new(); Self::preorder(root, 0, mut left_boundary, mut right_boundary, mut leaves); left_boundary.extend(leaves); left_boundary.extend(right_boundary); left_boundary } fn is_leaf(node: RcRefCellTreeNode) - bool { let n node.borrow(); n.left.is_none() n.right.is_none() } fn left_child_flag(cur: RcRefCellTreeNode, flag: i32) - i32 { if flag 1 || flag 0 { 1 } else if flag 2 cur.borrow().right.is_none() { 2 } else { 3 } } fn right_child_flag(cur: RcRefCellTreeNode, flag: i32) - i32 { if flag 2 || flag 0 { 2 } else if flag 1 cur.borrow().left.is_none() { 1 } else { 3 } } fn preorder( cur: OptionRcRefCellTreeNode, flag: i32, left_boundary: mut Veci32, right_boundary: mut Veci32, leaves: mut Veci32, ) { if let Some(node) cur { if flag 2 { right_boundary.insert(0, node.borrow().val); } else if flag 1 || flag 0 { left_boundary.push(node.borrow().val); } else if Self::is_leaf(node) { leaves.push(node.borrow().val); } let lf Self::left_child_flag(node, flag); let rf Self::right_child_flag(node, flag); let left node.borrow().left.clone(); let right node.borrow().right.clone(); Self::preorder(left, lf, left_boundary, right_boundary, leaves); Self::preorder(right, rf, left_boundary, right_boundary, leaves); } } }::tabs-end复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$其中 $n$ 为树中节点的个数。与解法一相同单次前序遍历仍然访问每个节点一次递归深度或显式栈与三个结果列表在极端情况下合计为 $O(n)$ 空间。常见陷阱Common Pitfalls1. 把叶子节点误收进左、右边界叶子节点应当只出现一次且只属于叶子部分。如果在遍历左/右边界时没有先判断isLeaf就直接把节点加入边界叶子会在结果中重复出现# 错误示范加入边界前未判断叶子 while t is not None: res.append(t.val) # 应当先判断if not isLeaf(t) t t.left if t.left else t.right正确做法是加入边界前先检查if not isLeaf(t)保证非叶子才进边界。2. 右边界顺序颠倒右边界必须以**自下而上bottom-to-top**的顺序输出。常见错误是在下行遍历过程中直接把节点按自上而下的顺序加入结果导致整体顺序错误。解法一用栈收集后统一弹出解法二用头部插入insert(0, ...)/unshift/add(0, ...)天然完成逆序两者本质相同。3. 忽略单子节点场景左边界下行时若某节点没有左孩子必须沿右孩子继续右边界反之亦然。如果在孩子缺失处直接停止遍历会漏掉更深处的边界节点尤其是退化链状树场景下会严重丢节点。两种方案对比与选型建议维度解法一三段拆分解法二单次前序遍历 标志位遍历次数三段独立遍历左边界、叶子、右边界一次前序遍历完成全部收集右边界逆序手段显式栈 弹出头部插入insert(0, ...)叶子去重边界遍历时需手动isLeaf过滤标志位分类天然隔离内部节点不收集实现复杂度直观易懂适合作为首选讲解需理解标志位传播规则一次遍历更优雅复杂度时间 $O(n)$空间 $O(n)$时间 $O(n)$空间 $O(n)$面试或教学场景推荐解法一思路直白、代码可读性强且与左边界 / 叶子 / 右边界的定义一一对应追求单次遍历或喜欢函数式风格时可选择解法二标志位设计把边界身份显式建模逻辑更紧凑。延伸阅读边界遍历综合运用了前序、中序、后序三类遍历思路也与叶子收集、树形结构判定密切相关可继续阅读仓库中的相关文章加深理解articles/binary-tree-preorder-traversal.md —— 前序遍历的递归与迭代实现解法二的基础articles/binary-tree-inorder-traversal.md 与 articles/binary-tree-postorder-traversal.md —— 另外两种遍历模式articles/leaf-similar-trees.md —— 叶子节点序列的收集与比较与本文的addLeaves思路一致。本仓库将各语言题解按目录组织python/、java/、cpp/、javascript/、go/、kotlin/、swift/、rust/等本文两套解法均已给出上述语言的标准实现可直接对照练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考