递归，迭代（单栈，Java 用 ArrayDeque 实现）2种方法后序遍历，求解《1022. 从根到叶的二进制数之和》
例题
1022. 从根到叶的二进制数之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个 32 位 整数。
示例 1：
输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
答案
后序遍历 · 递归
var sumRootToLeaf = function(root) {
const d = (n, val) => {
if (n === null) return 0
val = (val << 1) + n.val
if (n.left === null && n.right === null) return val
return d(n.left, val) + d(n.right, val)
}
return d(root, 0)
};function sumRootToLeaf(root: TreeNode | null): number {
const d = (n: TreeNode | null, val: number): number => {
if (n === null) return 0
val = (val << 1) + n.val
if (n.left === null && n.right === null) return val
return d(n.left, val) + d(n.right, val)
}
return d(root, 0)
};class Solution {
function sumRootToLeaf($root) {
return $this->d($root, 0);
}
function d($n, $val) {
if ($n === null) return 0;
$val = ($val << 1) + $n->val;
if ($n->left === null && $n->right === null) return $val;
return $this->d($n->left, $val) + $this->d($n->right, $val);
}
}func sumRootToLeaf(root *TreeNode) int {
var d func(n *TreeNode, val int) int
d = func(n *TreeNode, val int) int {
if n == nil {
return 0
}
val = val << 1 + n.Val
if n.Left == nil && n.Right == nil {
return val
}
return d(n.Left, val) + d(n.Right, val)
}
return d(root, 0)
}class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def d(n, val):
if n == None: return 0
val = (val << 1) + n.val
if n.left == None and n.right == None: return val
return d(n.left, val) + d(n.right, val)
return d(root, 0) class Solution {
public int sumRootToLeaf(TreeNode root) {
return d(root, 0);
}
public int d(TreeNode n, int val) {
if (n == null) return 0;
val = (val << 1) + n.val;
if (n.left == null && n.right == null) return val;
return d(n.left, val) + d(n.right, val);
}
}后序遍历 · 迭代 · 单栈
var sumRootToLeaf = function(root) {
const stack = []
let p = root, prev = null, sum = 0, val = 0
while (p || stack.length) {
while (p) {
val = (val << 1) + p.val
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
if (n.left === null && n.right === null) sum += val
val >>= 1
prev = n
} else {
stack.push(n)
p = n.right
}
}
return sum
};function sumRootToLeaf(root: TreeNode | null): number {
const stack = []
let p = root, prev = null, sum = 0, val = 0
while (p || stack.length) {
while (p) {
val = (val << 1) + p.val
stack.push(p)
p = p.left
}
const n = stack.pop()
if (n.right === null || n.right === prev) {
if (n.left === null && n.right === null) sum += val
val >>= 1
prev = n
} else {
stack.push(n)
p = n.right
}
}
return sum
};class Solution {
function sumRootToLeaf($root) {
$stack = [];
$p = $root;
$prev = null;
$sum = $val = 0;
while ($p || count($stack) > 0) {
while ($p) {
$val = ($val << 1) + $p->val;
$stack []= $p;
$p = $p->left;
}
$n = array_pop($stack);
if ($n->right === null || $n->right === $prev) {
if ($n->left === null && $n->right === null) $sum += $val;
$val >>= 1;
$prev = $n;
} else {
$stack []= $n;
$p = $n->right;
}
}
return $sum;
}
}func sumRootToLeaf(root *TreeNode) int {
stack, p, prev, val, sum := []*TreeNode{}, root, &TreeNode{}, 0, 0
for len(stack) > 0 || p != nil {
for p != nil {
val = val << 1 + p.Val
stack = append(stack, p)
p = p.Left
}
n := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if n.Right == nil || n.Right == prev {
if n.Left == nil && n.Right == nil {
sum += val
}
val >>= 1
prev = n
} else {
stack = append(stack, n)
p = n.Right
}
}
return sum
}class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
stack, p, prev, val, sum = [], root, None, 0, 0
while len(stack) > 0 or p != None:
while p != None:
val = (val << 1) + p.val
stack.append(p)
p = p.left
n = stack.pop()
if n.right == None or n.right == prev:
if n.left == None and n.right == None: sum += val
val >>= 1
prev = n
else:
stack.append(n)
p = n.right
return sumclass Solution {
public int sumRootToLeaf(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode p = root, prev = null;
int val = 0, sum = 0;
while (stack.size() > 0 || p != null) {
while (p != null) {
val = (val << 1) + p.val;
stack.push(p);
p = p.left;
}
TreeNode n = stack.pop();
if (n.right == null || n.right == prev) {
if (n.left == null && n.right == null) sum += val;
val >>= 1;
prev = n;
} else {
stack.push(n);
p = n.right;
}
}
return sum;
}
}