乐趣区

关于leetcode:LeetCode深度优先算法之树路径相关

jiezi

LeetCode 深度优先算法之树(门路相干)

树的问题个别都能够由深度优先算法和广度优先算法解决，门路相干的问题个别都能够用 DFS 或者基于 DFS 实现的回溯算法实现，咱们通过上面几道题来温习 & 训练 DFS 和回溯算法。

112. 门路总和

形容

给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。

阐明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及指标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在指标和为 22 的根节点到叶子节点的门路 5->4->11->2。

思路

首先，题目形容的是存在 从根节点到叶子节点的门路，也就是须要先确定什么状况下遍历到了叶子节点了。依据题目形容，叶子节点指的是没有左右节点的节点。

if (node.left == null && node.right == null)

sum 的和与其判断的是节点的总和，所以这是一个累加的和。咱们须要记录每个节点的和，先记录后遍历子节点，这种场景就是 dfs 典型的场景。

addVal();
recursion();

dfs 能够应用递归进行实现，目前曾经确定了能够应用 dfs 进行解决，递归的完结的条件是节点为 null 或者以后节点的左右节点为 null。还有一个问题，咱们如何确定以后叶子节点累加的值等于目标值呢？

if sum == node1.val + node2.val + node3.val;
then
   node3.val = sum - node2.val - node1.val;

所以咱们把子节点的目标值设置为 sum – curNode.val, 如果 curNode.val = target 的话，就代表存在一条从根节点到子节点的门路和等于目标值。

代码

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;
        if (root.left == null && root.right == null) return sum == root.val;

        return hasPathSum(root.left, sum - root.val) ||
                hasPathSum(root.right, sum - root.val);
    }
}

113. 门路总和 II

题目形容

给定一个二叉树和一个指标和，找到所有从根节点到叶子节点门路总和等于给定指标和的门路。

阐明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及指标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

思路

这道题是在 112. 门路总和的根底上扭转而来的，扭转的点是要记录所有和为目标值的门路。所以，这道题不能像 112 题那样满足条件后间接返回 boolean 类型，而是要全副遍历一遍直到满足条件为止，遇到这种穷举遍历判断是否满足指标条件的状况，能够应用回溯算法来解决这个问题。

回溯实质上也是 DFS，只不过是回溯个别应用一个对象进行记录节点的值，当门路节点遍历实现后，而后节点最初的值，防止分支净化。

代码

class Solution {List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {if (root == null) return res;

        List<Integer> list = new ArrayList<>();
        this.backTrack(list, root, sum);

        return res;
    }

    void backTrack(List<Integer> list, TreeNode node, int sum) {if (node == null) return ;

        list.add(node.val);
        if (node.left == null && node.right == null) {if (node.val == sum) {res.add(new ArrayList<>(list));
            }
            
            list.remove(list.size() - 1);
            return;
        }

        backTrack(list, node.left, sum - node.val);
        backTrack(list, node.right, sum - node.val);

        list.remove(list.size() - 1);
    }
}

129. 求根到叶子节点数字之和

题目形容

给定一个二叉树，它的每个结点都寄存一个 0-9 的数字，每条从根到叶子节点的门路都代表一个数字。

例如，从根到叶子节点门路 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

阐明: 叶子节点是指没有子节点的节点。

示例 1:

输出: [1,2,3]
    1
   / \
  2   3
输入: 25
解释:
从根到叶子节点门路 1->2 代表数字 12.
从根到叶子节点门路 1->3 代表数字 13.
因而，数字总和 = 12 + 13 = 25.
示例 2:

输出: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输入: 1026
解释:
从根到叶子节点门路 4->9->5 代表数字 495.
从根到叶子节点门路 4->9->1 代表数字 491.
从根到叶子节点门路 4->0 代表数字 40.
因而，数字总和 = 495 + 491 + 40 = 1026.

思路

透过景象看实质，[1,2,3]这种状况下，咱们对应的后果是 12+13=25。实际上，就是先记录左子树的值总和 + 右子树值总和，最初将总和值相加，这不就是后序遍历么。

recordValue();
recursion(left);
recursion(right);

既然是后序遍历，实际上也就是 DFS。咱们还有两个问题须要解决，第一是如果将以后节点的值进行累加，第二是递归的完结条件。

第一个问题，实际上 curVal = preNum * 10 + node.val，递归过程中只有记录 preNum 的参数就好了，preNum 的初始值就是 0。

第二个问题就是递归的完结条件，其实就是遍历到叶子节点。叶子节点也就是左节点和右节点为空。

代码

class Solution {public int sumNumbers(TreeNode root) {if (root == null) return 0;
        
        return dfs(root, 0);
    }
    
    int dfs(TreeNode root, int preNum) {if (root == null) return 0;
        
        int num = preNum * 10 + root.val;
        if (root.left == null && root.right == null) return num;
        
        int leftSum = dfs(root.left, num);
        int rightSum = dfs(root.right, num);
        
        return leftSum + rightSum;
    }
}

257. 二叉树的所有门路

题目形容


给定一个二叉树，返回所有从根节点到叶子节点的门路。阐明: 叶子节点是指没有子节点的节点。示例:

输出:

   1
 /   \
2     3
 \
  5

输入: ["1->2->5", "1->3"]

思路

所有门路问题第一想法就是回溯，然而这道题不同的是存在一个非凡的字符串 ->，回溯删除元素的时候要思考这种场景，所以在删除节点之前记录以后字符串的索引地位，这样就能够应用 stringBuilder.deleteCharAt(index, cur.length());

代码

class Solution {List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {if (root == null) return res;

        this.backTrack(new StringBuilder(""), root);
        return res;
    }

    public void backTrack(StringBuilder sb, TreeNode node) {if (node == null) return;

        if (node.left == null && node.right == null) {res.add(sb.toString() + node.val);
            return;            
        }

        int delIndex = sb.length();
        sb.append(node.val).append("->");
        backTrack(sb, node.left);
        backTrack(sb, node.right);

        sb.delete(delIndex, sb.length());
    }
}

程序员面试金典 04.12 求和门路

题目形容

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有门路的数量。留神，门路不肯定非得从二叉树的根节点或叶节点开始或完结，然而其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树，以及指标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

3
解释：和为 22 的门路有：[5,4,11,2], [5,8,4,5], [4,11,7]
提醒：

节点总数 <= 10000

思路

这道题和下面题不同的是，门路不要求是从根节点开始遍历的。所以咱们须要记录每层节点的值，先通过递归算法确定树的深度，而后依据以后深度进行赋值，遍历以后深度对应值直到深度为 0 为止，如果遍历的和等于 sum，那么数量 +1

代码

class Solution {

    int res = 0;
    public int pathSum(TreeNode root, int sum) {if (root == null) return res;

        int depth = depth(root);
        int[] levels = new int[depth];
        this.bfs(root, levels, 0, sum);

        return res;
    }

    void bfs(TreeNode root, int[] levels, int level, int num) {if (root == null) return;

        levels[level] = root.val;
        int sum = 0;
        for (int i = level; i >= 0; i--) {sum += levels[i];
            if (sum == num) {res += 1;}
        }

        bfs(root.left, levels, level + 1, num);
        bfs(root.right, levels, level + 1, num);
    }


    int depth(TreeNode root) {if (root == null) return 0;

        int left = depth(root.left);
        int right = depth(root.right);
        
        return left > right ? left + 1 : right + 1;
    }
}
退出移动版