关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
路径遍历
LeetCode题目：257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
class Solution {
public List<List<Integer>> allPath = new ArrayList<List<Integer>>();
public List<Integer> path = new ArrayList<Integer>();
public List<String> binaryTreePaths(TreeNode root) {
getAllPath(root);
List<String> result = new ArrayList<String>();
for(List<Integer> path : allPath) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < path.size() - 1; i++) {
sb.append(path.get(i) + "->");
}
sb.append(path.get(path.size() - 1));
result.add(sb.toString());
}
return result;
}
public void getAllPath(TreeNode root) {
if(root == null) return;
path.add(root.val);
// if is leaf, add one path
if(root.left == null && root.right == null) {
allPath.add(new ArrayList(path));
}
else {
getAllPath(root.left);
getAllPath(root.right);
}
// backtracking
path.remove(path.size() - 1);
}
}
LeetCode题目：129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
Sum Root to Leaf Numbers
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
class Solution {
int sum = 0;
StringBuilder path = new StringBuilder();
public int sumNumbers(TreeNode root) {
dfs(root);
return sum;
}
public void dfs(TreeNode root) {
if(root == null) return;
path.append(root.val);
// 达到叶子节点，累加sum
if(root.left == null && root.right == null) {
sum = sum + Integer.parseInt(path.toString());
}
else {
dfs(root.left);
dfs(root.right);
}
// backtracking
path = path.deleteCharAt(path.length() - 1);
}
}
LeetCode题目：298. Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
class Solution {
int maxLength = 0;
public int longestConsecutive(TreeNode root) {
dfs(root);
return maxLength;
}
public int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left) + 1;
int right = dfs(node.right) + 1;
if (node.left != null && node.val + 1 != node.left.val) {
left = 1;
}
if (node.right != null && node.val + 1 != node.right.val) {
right = 1;
}
int length = Math.max(left, right);
maxLength = Math.max(maxLength, length);
return length;
}
}
LeetCode题目：687. Longest Univalue Path
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
Note: The length of path between two nodes is represented by the number of edges between them.
class Solution {
int maxLength = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return maxLength;
}
// 以node.val为值的最长单边path
public int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
int arrowLeft = 0;
if (node.left != null && node.left.val == node.val) {
arrowLeft = left + 1;
}
int arrowRight = 0;
if (node.right != null && node.right.val == node.val) {
arrowRight = right + 1;
}
maxLength = Math.max(maxLength, arrowLeft + arrowRight);
return Math.max(arrowLeft, arrowRight);
}
}
路径求和
LeetCode题目：112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
// if leaf
if(root.left == null && root.right == null) {
if(root.val == sum) {
return true;
}
else {
return false;
}
}
// if not leaf, recursive on left sub tree and right sub tree
else {
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
}
LeetCode题目：113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
class Solution {
public List<List<Integer>> allPath = new ArrayList<List<Integer>>();
public List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
getAllPath(root);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(List<Integer> path : allPath) {
int t = 0;
for(Integer i : path) {
t = t + i;
}
if(t == sum) {
result.add(path);
}
}
return result;
}
public void getAllPath(TreeNode root) {
if(root == null) return;
path.add(root.val);
// if is leaf, add one path
if(root.left == null && root.right == null) {
allPath.add(new ArrayList(path));
}
else {
getAllPath(root.left);
getAllPath(root.right);
}
// backtracking
path.remove(path.size() - 1);
}
}
LeetCode题目：437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
class Solution {
public List<List<Integer>> allPath = new ArrayList<List<Integer>>();
public List<Integer> path = new ArrayList<Integer>();
public int pathSum(TreeNode root, int sum) {
DFS(root, sum);
return allPath.size();
}
public void DFS(TreeNode root, int sum) {
if(root != null) {
travel(root, sum);
DFS(root.left, sum);
DFS(root.right, sum);
}
}
public void travel(TreeNode root, int sum) {
if(root == null) return;
path.add(root.val);
if(root.val == sum) {
allPath.add(new ArrayList(path));
}
travel(root.left, sum - root.val);
travel(root.right, sum - root.val);
// backtracking
path.remove(path.size() - 1);
}
}
网友评论