后序遍历写法(非递归写法)基础上更改 直接得到答案的 小白易理解 题解 | #二叉树根节点到叶子节点的所有路径和#

bfs(非递归 while循环实现的后序遍历) 该题可视作后序遍历的变种(原因画图后,很容易得出),直接写出该题的代码并理解其逻辑可能有些复杂,故而我们从后序遍历的代码开始,改为该题的解法代码,可以降低理解的思维难度:

常规后序遍历代码:(当然,如果对你来说不够常规或者根本没有印象的话,只能说数据结构与算法基本功不扎实)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // write code here
        Stack<TreeNode> nodeStack = new Stack<>();
        //本题在dfs基础上,添加了两个关键点
        //1.引入valueStack,存储值
        //Stack<Integer> valueStack = new Stack<>();
        //valueStack.push(0);
        TreeNode node = root;
        int total=0;
        while(node!=null || !nodeStack.isEmpty()){
            if(node!=null){
                //valueStack栈每深入一层,值都=上一层值*10+当前层的值
                valueStack.push(valueStack.peek()*10+node.val);
                nodeStack.push(node);
                node=node.left;
            }else{
                node=nodeStack.pop();
                //只有当该node为空节点时,才把valueStack栈顶的值加入total
                //if(node.left==null&&node.right==null){
                  //  total+=valueStack.peek();
                //}
                 visit(node);//visit()是要node节点的遍历方式,视问题而定
                //valueStack.pop()
                node=node.right;
            }
        }
        return total;
    }
    
}

以上代码 作为 后序遍历写法(非递归写法)的通用模板(注释部分是为了方便和下面本题的解法代码相对比),极大的降低了 代码编写难度!

本体解法代码:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // write code here
        Stack<TreeNode> nodeStack = new Stack<>();
        //本题在dfs基础上,添加了两个关键点
        //1.引入valueStack,存储值
        Stack<Integer> valueStack = new Stack<>();
        valueStack.push(0);
        TreeNode node = root;
        //r是后序遍历所需的一个指针,用于记录最近访问过的节点
        TreeNode r=null;
        int total=0;
        while(node!=null || !nodeStack.isEmpty()){
            if(node!=null){
                //valueStack栈每深入一层,值都=上一层值*10+当前层的值
                valueStack.push(valueStack.peek()*10+node.val);
                nodeStack.push(node);
                node=node.left;
            }else{
                node=nodeStack.peek();
                if(node.right!=null&&node.right!=r){
                    node=node.right;
                }else{
                    node=nodeStack.pop();
                    
                    //只有当该node为空节点时,才把valueStack栈顶的值加入total
                    if(node.left==null&&node.right==null){
                        total+=valueStack.peek();
                    }
                    valueStack.pop();
                    r=node;
                    node=null;
                }
            }
        }
        return total;
    }
}

画图后很容易体会出valueStack的妙处,它的引入是本题的思考难度的主要来源!