题解 | #二叉树根节点到叶子节点的所有路径和#
二叉树根节点到叶子节点的所有路径和
http://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83
非递归实现,利用手动建栈来代替函数堆栈的实现方式。 情况总共分为三种情况,
- 父节点含有左右子节点。
- 父节点只有其中一边子节点。
- 父节点没有子节点。
如果要使用DFS深度遍历优先的方式来完成,则需要关注三个重点,就是路径选择的方向与路径是否重复以及路径计算保存的问题。
根据问题1路径选择方向,引入direction变量来判断方向。 根据问题2路径是否重复,选择以左边方向为默认,根据父节点拥有的子节点情况来选择方向以及是否将父节点压栈保留记录。 根据问题3路径计算保存,选择以更改子节点权值来进行保存。
JavaScript代码实现如下:
const sumNumbers = (root) => {
// write code here
// DFS
let sum = 0;
let eachRouteVal = 0;
let nodeStack = [];
let currentNode = root;
let parent = null;
let child = null;
let direction = true; //true means left, false means right
if (!root) return 0;
if (!root.left && !root.right) return root.val;
while (currentNode || !queueIsEmpty(nodeStack)) {
parent = currentNode;
if (currentNode.left || currentNode.right) {
// only push parent got two children into stack,because of two path
if (currentNode.left && currentNode.right) {
if (direction) {
nodeStack.push(currentNode);
}
child = direction ? currentNode.left : currentNode.right;
} else{
direction = currentNode.left ? true : false;
child = direction ? currentNode.left : currentNode.right;
}
eachRouteVal = calculateRouteValue(parent, child);
child.val = eachRouteVal;
currentNode = child;
direction = true; //start from left route by default
} else {
// solve the right path
currentNode = nodeStack.pop();
sum += eachRouteVal;
eachRouteVal = 0;
direction = false;
}
}
return sum;
}
const queueIsEmpty = (queue) =>{
return queue.length === 0;
}
const calculateRouteValue = (parent,child) => {
return parseInt([String(parent.val),String(child.val)].join(''));
}