NC9 二叉树中是否存在节点和为指定值的路径

题目描述

给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径，

方法一： 暴力递归

解题思路

因为题目中所说的路径是从根节点到叶子节点所有节点走完，而二叉树里可以用前序遍历、中序遍历、后序遍历从根节点往下一条一条地遍历到叶子节点。

我们需要做的就是在这遍历的过程中，把每个节点的值加起来，到叶子节点的时候，判断这些加起来的值是不是等于指定值就可以了。如果相等，那么我们就找到了存在这样的一条路劲；如果不相等，则不存在。

这里就以前序遍历这个方式进行说明：所有我们自己的操作都在进行左右子树遍历之前进行，即相加操作的代码都在遍历左右子树之前书写。具体思路参考下面提供的代码。

回顾整个操作，大体的思路就是找到所有的路径，再挨个判断每个路径是否符合条件，不符合就继续玩下找，直到找完了；符合就直接返回即可，无需再往下找。

以下是 targetSum 为 9 时的演示示例：
图片说明

复杂度

时间复杂度：O(N)

  • 递归遍历每个节点，每个节点都需要遍历访问到，总共右N个节点，时间复杂度即为O(N)。

空间复杂度：O(N)

  • 递归需要用到栈结构，开辟的栈空间和树的高度有关，即O(h), h 为该二叉树的高度，即O(logN);但最坏的情况下，可以把每个节点都压入栈中，即空间复杂度可以达到 O(N)。

示例代码

public class Solution {
    /**
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // 判断特殊情况
        if (root == null) {
            return false;
        }

        return preOrder(root, root.val, sum);
    }


    /**
     * @param root 当前走到的节点，TreeNode类 
     * @param curSum 走到当前节点时的“节点和” 
     * @param targetSum “节点和”的指定值
     * @return 
     */
    public boolean preOrder(TreeNode root, int curSum, int targetSum){
        // 到达叶子节点,也就是有一条路径，之后再判断这个路径符不符合条件
        if (root.left == null && root.right == null) {
            // 存在节点和为指定值，符合条件
            if (curSum == targetSum) {
                return true;
            }
            return false;
        }

        // 递归进去防止空指针异常，加个判断
        if (root.left != null) {
            // 遍历左子树，看左子树有没有这样的路径
            boolean b1 = preOrder(root.left, curSum+root.left.val, targetSum);
            // 找到这样的路径，直接返回 true
            if (b1) {
                return true;
            }            
        }
        if (root.right != null) {
            // 遍历右子树，看右子树有没有这样的路径
            boolean b2 = preOrder(root.right, curSum+root.right.val,targetSum);
            if (b2) {
                return true;
            }            
        }

        // 左右子树都没有这样的路径，直接返回 false 不存在
        return false;
    }


}

方法二： 用栈

解题思路

之前用的是二叉树的递归遍历形式找路径。 我们知道用栈结构可以将递归方式改写为非递归方式，所以也可以使用栈结构来解决该题。

对于先序遍历，非递归的方式就是：先用栈保存头节点，因为栈结构的特性是后进先出，所以我们先压右节点，再压左节点，这样到后面弹出就是先弹左节点，再弹右节点。对于先序遍历是如此，但此题只要求我们找路径，所以先遍历哪个子树的顺序并不是关键点。

关键的地方仍然在于，在遍历的过程中，记录下每个节点的路径和，到叶子节点的时候，就判断此时的路径和是不是目标值即可。

以下是 targetSum 为 9 时的演示示例：
图片说明

具体实现方式请参考代码。

复杂度

较方法一而言并没有优化多少，只是使用的栈结构是我们自己定义的而已。
时间复杂度：O(N)

  • 每个节点都需要挨个访问左右节点，共有N个节点需要遍历访问到，即时间复杂度为O(N)。

空间复杂度：O(N)

  • 极端情况下，一开始一直往左节点访问，它的所有右节点存储到栈空间中，此时栈空间达到最大，之后会从栈里弹出元素，所以开辟的栈空间和该二叉树的高度有关，即空间复杂度为O(h)，h为该二叉树的高度，即O(logN)；
    但最坏的情况下，可以把每个节点都压入栈中，即空间复杂度可以达到 O(N)。

示例代码

public class Solution {

    // 保存 节点 和 节点对应的路径和 的自定义类
    class Node{
        TreeNode node; // 节点
        int sum;       // 节点对应的路径和

        public Node(TreeNode node, int sum){
            this.node = node;
            this.sum = sum;
        }
    }

    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // 判断特殊情况
        if (root == null) {
            return false;
        }


        // 用栈解决该问题， 栈里装的是自定义的 Node 类。
        Stack<Node> stack = new Stack<>();
        // 先压头节点
        stack.push(new Node(root, root.val));
        while (!stack.isEmpty()) {
            Node popNode = stack.pop();
           TreeNode node = popNode.node;

            // 此时弹出的是叶子节点
            if (node.left == null && node.right == null) {
                // 路径和是否等于指定值
                if (popNode.sum == sum) {
                    return true;
                }  
            }

            // 如果右孩子不为空，就压右孩子
            if (node.right != null) {
                // 压节点的时候， 把对应节点的路径和也记录上
                stack.push( new Node(node.right, popNode.sum + node.right.val));
            }

            // 如果左孩子不为空，就压左孩子
            if (node.left != null) {
                // 压节点的时候， 把对应节点的路径和也记录上
                stack.push( new Node(node.left, popNode.sum + node.left.val));
            }
        }

        // 整个遍历过程结束，还没有找到符合条件的路径，就返回 false
        return false;
    } 

}