当前位置：首页 > news >正文

迭代法求从根到叶的二进制数之和

news 2026/7/3 18:25:29

迭代

我们用栈来模拟递归，同时使用一个 prev 指针来记录先前访问的节点。算法步骤如下：

如果节点 root 非空，我们将不断地将它及它的左节点压入栈中。

我们从栈中获取节点：

该节点的右节点为空或者等于 prev ，说明该节点的左子树及右子树都已经被访问，我们将它出栈。如果该节点是叶子节点，我们将它对应的数字 val 加入结果中。设置 prev 为该节点，设置 root 为空指针。

该节点的右节点非空且不等于 prev ,我们令 root 指向该节点的右节点。

3.如果 root 为空指针或者栈空，中止算法，否则重复步骤 1。

需要注意的是，每次出入栈都需要更新 val 。

代码

Python3

class Solution: def sumRootToLeaf(self, root: Optional[TreeNode]) -> int: ans = val = 0 st = [] pre = None while root or st: while root: val = (val << 1) | root.val st.append(root) root = root.left root = st[-1] if root.right is None or root.right == pre: if root.left is None and root.right is None: ans += val val >>= 1 st.pop() pre = root root = None else: root = root.right return ans

Java

class Solution { public int sumRootToLeaf(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); int val = 0, ret = 0; TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { val = (val << 1) | root.val; stack.push(root); root = root.left; } root = stack.peek(); if (root.right == null || root.right == prev) { if (root.left == null && root.right == null) { ret += val; } val >>= 1; stack.pop(); prev = root; root = null; } else { root = root.right; } } return ret; } }

C++

class Solution { public: int sumRootToLeaf(TreeNode* root) { stack<TreeNode *> st; int val = 0, ret = 0; TreeNode *prev = nullptr; while (root != nullptr || !st.empty()) { while (root != nullptr) { val = (val << 1) | root->val; st.push(root); root = root->left; } root = st.top(); if (root->right == nullptr || root->right == prev) { if (root->left == nullptr && root->right == nullptr) { ret += val; } val >>= 1; st.pop(); prev = root; root = nullptr; } else { root = root->right; } } return ret; } };

复杂度分析