深度优先搜索思路
深度优先搜索 = 回溯法
可以通过遍历或者分治法的思想实现深度优先搜索
而递归和迭代 (非递归)两种代码实现方式来做遍历和分治
这种题就是这两种思路 遍历或者分治 遇到了两种思路都想一想 顶多就是函数多传一些参数传递更多信息
深度优先搜索题目
111 Minimum Depth of Binary Tree (注意叶节点的判断）分治/bfs
104 Maxmum Depth of Binary Tree 分治/bfs
112 Path Sum 是否存在根到叶节点路径和为target 分治递归/遍历dfs非递归
113 Path Sum II 求所有路径 分治(递归)/遍历递归/遍历dfs非递归/遍历bfs非递归
124 Binary Tree Maximum Path Sum 求最长路径值（可以不通过根结点 可以不通过叶节点）分治(递归)/后序遍历
129 Sum Root to Leaf Numbers 到叶子节点所有路径和 dfsRecursion/dfsIteration
lt596 Minimum Subtree 求最小子树 返回根结点
lt480 Binary Tree Paths 求所有从根结点到叶节点的路径
lt88. Lowest Common Ancestor of a Binary Tree
lt578. Lowest Common Ancestor III
lt474. Lowest Common Ancestor II
preorder
inorder
postorder
114 Flatten Binary Tree to Linked List
111. Minimum Depth of Binary Tree
求到叶节点最小距离 两种方法
bfs 找第一个没有左右儿子的
分治 注意是到叶节点
class Solution {
public int minDepth(TreeNode root) {
return bfs(root);
// return divideConque(root);
}
public int bfs(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int height = 0;
while(!queue.isEmpty()){
height++;
int size = queue.size();
for(int i=0; i<size; i++){
TreeNode node = queue.poll();
if(node.left==null && node.right==null)
return height;
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
}
return -1;
}
public int divideConque(TreeNode root) {
if(root==null)
return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if(left==0)
return right+1;
if(right==0)
return left+1;
return Math.min(left,right)+1;
}
}
104. Maxmum Depth of Binary Tree
求到叶节点最大距离 两种方法
bfs
分治
class Solution {
public int maxDepth(TreeNode root) {
return bfs(root);
return recursive(root);
}
public int recursive(TreeNode root) {
if(root==null)
return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return 1+Math.max(left, right);
}
public int bfs(TreeNode root){
int height = 0;
if(root==null)
return height;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
height++;
for(int i=0; i<size; i++){
TreeNode node = queue.poll();
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
}
return height;
}
}
112. Path Sum
求是否存在到叶节点的路径 路径和为sum
dfs
分治
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root, sum);
}
public boolean dfs(TreeNode root, int sum) {
if(root==null)
return false;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> valStack = new Stack<>();
nodeStack.push(root);
valStack.push(sum);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
int value = valStack.pop();
if(node.left==null && node.right==null && node.val==value)
return true;
if(node.right!=null){
nodeStack.push(node.right);
valStack.push(value-node.val);
}
if(node.left!=null){
nodeStack.push(node.left);
valStack.push(value-node.val);
}
}
return false;
}
public boolean recursive(TreeNode root, int sum) {
if(root==null)
return false;
if(root.val==sum && root.left==null && root.right==null)
return true;
boolean left = hasPathSum(root.left, sum-root.val);
boolean right = hasPathSum(root.right, sum-root.val);
return left||right;
}
}
113. Path Sum II
求所有到叶节点路径和为sum的路径
分治(递归)/遍历递归/遍历dfs非递归/遍历bfs非递归
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// return bfs(root, sum);
return dfsRecursive(root, sum);
// return dfs(root, sum);
// return divideAndConque(root, sum);
}
public List<List<Integer>> dfsRecursive(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if(root==null){
return results;
}
List<Integer> result = new ArrayList<Integer>();
result.add(root.val);
helper(root, result, results, root.val, sum);
return results;
}
public void helper(TreeNode root, List<Integer> result, List<List<Integer>> results, int currentsum, int targetsum) {
if(currentsum==targetsum && root.left==null && root.right==null){
results.add(new ArrayList<Integer>(result));
return;
}
if(root.left!=null){
result.add(root.left.val);
helper(root.left, result, results, currentsum+root.left.val, targetsum);
result.remove(result.size()-1);
}
if(root.right!=null){
result.add(root.right.val);
helper(root.right, result, results, currentsum+root.right.val, targetsum);
result.remove(result.size()-1);
}
}
public List<List<Integer>> dfsNonrecursive(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
Stack<Integer> valStack = new Stack<>();
Stack<TreeNode> nodeStack = new Stack<>();
Stack<List<Integer>> listStack = new Stack<>();
List<Integer> result = new ArrayList<>();
valStack.push(root.val);
nodeStack.push(root);
result.add(root.val);
listStack.push(result);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
int value = valStack.pop();
List<Integer> list = listStack.pop();
if(node.left==null && node.right==null && value==sum)
results.add(new ArrayList<>(list));
if(node.left!=null){
valStack.push(value+node.left.val);
nodeStack.push(node.left);
List<Integer> temp = new ArrayList<>(list);
temp.add(node.left.val);
listStack.push(temp);
}
if(node.right!=null){
valStack.push(value+node.right.val);
nodeStack.push(node.right);
List<Integer> temp = new ArrayList<>(list);
temp.add(node.right.val);
listStack.push(temp);
}
}
return results;
}
public List<List<Integer>> bfs(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
Queue<TreeNode> nodeQueue = new LinkedList<>();
Queue<Integer> valQueue = new LinkedList<>();
Queue<List<Integer>> pathQueue = new LinkedList<>();
nodeQueue.offer(root);
valQueue.offer(root.val);
List<Integer> temp = new ArrayList<>();
temp.add(root.val);
pathQueue.offer(temp);
while(!nodeQueue.isEmpty()){
TreeNode node = nodeQueue.poll();
int value = valQueue.poll();
List<Integer> path = pathQueue.poll();
if(value==sum && node.left==null && node.right==null){
results.add(new ArrayList<>(path));
}
if(node.left!=null){
nodeQueue.offer(node.left);
valQueue.offer(value+node.left.val);
List<Integer> newpath = new ArrayList<>(path);
newpath.add(node.left.val);
pathQueue.offer(newpath);
}
if(node.right!=null){
nodeQueue.offer(node.right);
valQueue.offer(value+node.right.val);
List<Integer> newpath = new ArrayList<>(path);
newpath.add(node.right.val);
pathQueue.offer(newpath);
}
}
return results;
}
public List<List<Integer>> divideAndConque(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
if(root.left==null && root.right==null && root.val==sum){
List<Integer> temp = new ArrayList<Integer>();
temp.add(root.val);
results.add(temp);
return results;
}
List<List<Integer>> left = pathSum(root.left, sum-root.val);
List<List<Integer>> right = pathSum(root.right, sum-root.val);
if(left.size()!=0){
for(List<Integer> temp : left){
List<Integer> result = new ArrayList<>(temp);
result.add(0,root.val);
results.add(result);
}
}
if(right.size()!=0){
for(List<Integer> temp : right){
List<Integer> result = new ArrayList<>(temp);
result.add(0,root.val);
results.add(result);
}
}
return results;
}
}
124. Binary Tree Maximum Path Sum
求最长路径值（可以不通过根结点 可以不通过叶节点）
recursive
iterative
public class Solution {
public int maxPathSum(TreeNode root) {
// return recursiveWay(root);
// return iteratorWay(root);
return maxSubtree(root);
}
int max = Integer.MIN_VALUE;
public int recursiveWay(TreeNode root) {
helper(root);
return max;
}
// helper returns the max branch
// plus current node's value
int helper(TreeNode root) {
if(root==null)
return 0;
int left = Math.max(0, helper(root.left));
int right = Math.max(0, helper(root.right));
max = Math.max(max, left+right+root.val);
return root.val+Math.max(left, right);
}
public int iteratorWay(TreeNode root) {
int result = Integer.MIN_VALUE;
Map<TreeNode, Integer> maxRootPath = new HashMap<>(); // cache
maxRootPath.put(null, 0); // for simplicity we want to handle null nodes
for (TreeNode node : topSort(root)) {
// as we process nodes in post-order their children are already cached
int left = Math.max(maxRootPath.get(node.left), 0);
int right = Math.max(maxRootPath.get(node.right), 0);
maxRootPath.put(node, Math.max(left, right) + node.val);
result = Math.max(left + right + node.val, result);
}
return result;
}
public Deque<TreeNode> topSort(TreeNode root) {
// 用Deque的意义是 要按后序遍历 而Deque的遍历顺序就是先push的后遍历到
Deque<TreeNode> result = new LinkedList<>();
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
result.push(curr);
if (curr.left != null) stack.push(curr.left);
if (curr.right != null) stack.push(curr.right);
}
}
return result;
}
// follow up 求最大子树和
private int maxSubtree(TreeNode root){
helperMaxSubtree(root);
return max;
}
private int helperMaxSubtree(TreeNode root){
if(root==null)
return 0;
int left = helperMaxSubtree(root.left);
int right = helperMaxSubtree(root.right);
max = Math.max(left+right+root.val, max);
return left+right+root.val;
}
}
129. Sum Root to Leaf Numbers
到叶子节点路径和
class Solution {
public int sumNumbers(TreeNode root) {
return recursion(root);
// return dfsIteration(root);
}
int total = 0;
public int recursion(TreeNode root) {
helper(root, 0);
return total;
}
public void helper(TreeNode node, int sum){
if(node==null)
return;
sum = sum*10 + node.val;
if(node.left==null && node.right==null){
//只有是叶节点 才加到总和里
total = total + sum;
return;
}
helper(node.left, sum);
helper(node.right, sum);
}
public int dfsIteration(TreeNode root) {
if(root==null)
return 0;
int result = 0;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> valStack = new Stack<>();
nodeStack.push(root);
valStack.push(0);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
int val = valStack.pop();
val = val*10 + node.val;
if(node.left==null && node.right==null){
result = result + val;
}
if(node.right!=null){
nodeStack.push(node.right);
valStack.push(val);
}
if(node.left!=null){
nodeStack.push(node.left);
valStack.push(val);
}
}
return result;
}
}
lt596. Minimum Subtree
public class Solution {
/**
* @param root: the root of binary tree
* @return: the root of the minimum subtree
*/
TreeNode result = null;
int min = Integer.MAX_VALUE;
public TreeNode findSubtree(TreeNode root) {
// write your code here
helper(root);
return result;
}
public int helper(TreeNode node){
if(node==null)
return 0;
int left = helper(node.left);
int right = helper(node.right);
int sum = left+right+node.val;
if(sum<min){
result = node;
min = sum;
}
return sum;
}
}
//纯divide conque
class ResultType {
public TreeNode minSubtree;
public int sum, minSum;
public ResultType(TreeNode minSubtree, int minSum, int sum) {
this.minSubtree = minSubtree;
this.minSum = minSum;
this.sum = sum;
}
}
public class Solution {
/**
* @param root the root of binary tree
* @return the root of the minimum subtree
*/
public TreeNode findSubtree(TreeNode root) {
ResultType result = helper(root);
return result.minSubtree;
}
public ResultType helper(TreeNode node) {
if (node == null) {
return new ResultType(null, Integer.MAX_VALUE, 0);
}
ResultType leftResult = helper(node.left);
ResultType rightResult = helper(node.right);
ResultType result = new ResultType(
node,
leftResult.sum + rightResult.sum + node.val,
leftResult.sum + rightResult.sum + node.val
);
if (leftResult.minSum <= result.minSum) {
result.minSum = leftResult.minSum;
result.minSubtree = leftResult.minSubtree;
}
if (rightResult.minSum <= result.minSum) {
result.minSum = rightResult.minSum;
result.minSubtree = rightResult.minSubtree;
}
return result;
}
}
lt480. Binary Tree Paths
//divide and conque
public class Solution {
/**
* @param root: the root of the binary tree
* @return: all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
// write your code here
List<String> result = new ArrayList<>();
if(root==null)
return result;
if(root.left==null && root.right==null){
result.add(""+root.val);
return result;
}
List<String> left = binaryTreePaths(root.left);
List<String> right = binaryTreePaths(root.right);
for(String temp : left){
result.add(root.val+"->"+temp);
}
for(String temp : right){
result.add(root.val+"->"+temp);
}
return result;
}
}
//traverse
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<String>();
if (root == null) {
return result;
}
helper(root, String.valueOf(root.val), result);
return result;
}
private void helper(TreeNode root, String path, List<String> result) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
result.add(path);
return;
}
//这里如果记录的是path list 然后最后拼接效率更高
if (root.left != null) {
//path.add()
helper(root.left, path + "->" + String.valueOf(root.left.val), result);
//path.remove()
}
if (root.right != null) {
//path.add()
helper(root.right, path + "->" + String.valueOf(root.right.val), result);
//path.remove()
}
}
}
lt88. Lowest Common Ancestor of a Binary Tree
public class Solution {
/*
* @param root: The root of the binary search tree.
* @param A: A TreeNode in a Binary.
* @param B: A TreeNode in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
if(root==null)
return null;
if(A==root || B==root)
return root;
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
if(left!=null && right!=null)
return root;
if(left!=null)
return left;
if(right!=null)
return right;
return null;
}
}
lt578. Lowest Common Ancestor III
public class Solution {
/*
* @param root: The root of the binary tree.
* @param A: A TreeNode
* @param B: A TreeNode
* @return: Return the LCA of the two nodes.
*/
class ResultType{
boolean hasA, hasB;
TreeNode node;
ResultType(boolean hasA, boolean hasB, TreeNode result){
this.hasB = hasB;
this.hasA = hasA;
this.node = result;
}
}
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
ResultType result = helper(root, A, B);
return result.node;
}
public ResultType helper(TreeNode root, TreeNode A, TreeNode B){
if(root==null){
ResultType result = new ResultType(false, false, null);
return result;
}
ResultType left = helper(root.left, A, B);
ResultType right = helper(root.right, A, B);
if(left.node!=null){
return left;
}
if(right.node!=null){
return right;
}
boolean hasA = left.hasA || right.hasA || root==A;
boolean hasB = left.hasB || right.hasB || root==B;
ResultType result = new ResultType(hasA, hasB, null);
if(hasA && hasB){
result.node = root;
return result;
}
return result;
}
}
lt474. Lowest Common Ancestor II
public class Solution {
/*
* @param root: The root of the tree
* @param A: node in the tree
* @param B: node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
// write your code here
if(A==root || B==root)
return root;
List<ParentTreeNode> listA = new ArrayList<>();
List<ParentTreeNode> listB = new ArrayList<>();
while(A!=null){
listA.add(0, A);
A = A.parent;
}
while(B!=null){
listB.add(0, B);
B = B.parent;
}
int index = 0;
while(index<listA.size() && index<listB.size()){
if(listA.get(index) != listB.get(index))
return listA.get(index-1);
index++;
}
return listA.get(index-1);
}
}
preorder
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// return modelPre(root);
return recursive(root);
}
public List<Integer> recursive(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root==null){
return result;
}
helper(root, result);
return result;
}
public void helper(TreeNode root, List<Integer> result) {
result.add(root.val);
if(root.left!=null)
helper(root.left, result);
if(root.right!=null)
helper(root.right, result);
}
public List<Integer> iterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root==null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if(node.right!=null)
stack.push(node.right);
if(node.left!=null)
stack.push(node.left);
}
return result;
}
public enum Operation{
PROCESSING,
ADDRESULT
}
public List<Integer> modelPre(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)
return res;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Operation> operationStack = new Stack<>();
nodeStack.push(root);
operationStack.push(Operation.PROCESSING);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
Operation operation = operationStack.pop();
if(node==null)
continue;
if(operation == Operation.ADDRESULT){
res.add(node.val);
}
else{
nodeStack.push(node.right);
operationStack.push(Operation.PROCESSING);
nodeStack.push(node.left);
operationStack.push(Operation.PROCESSING);
nodeStack.push(node);
operationStack.push(Operation.ADDRESULT);
}
}
return res;
}
}
inorder
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
return modelIn(root);
}
public List<Integer> inorderClassical(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)
return res;
Stack<TreeNode> stack = new Stack<>();
while(root!=null){
stack.push(root);
root = root.left;
}
while(!stack.isEmpty()){
TreeNode node = stack.peek();
res.add(node.val);
if(node.right!=null){
node = node.right;
while(node!=null){
stack.push(node);
node = node.left;
}
}else{
node = stack.pop();
while(!stack.isEmpty() && node!=stack.peek().left){
node = stack.pop();
}
}
}
return res;
}
public enum Operation{
PROCESSING,
ADDRESULT
}
public List<Integer> modelIn(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)
return res;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Operation> operationStack = new Stack<>();
nodeStack.push(root);
operationStack.push(Operation.PROCESSING);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
Operation operation = operationStack.pop();
if(node==null)
continue;
if(operation == Operation.ADDRESULT){
res.add(node.val);
}
else{
nodeStack.push(node.right);
operationStack.push(Operation.PROCESSING);
nodeStack.push(node);
operationStack.push(Operation.ADDRESULT);
nodeStack.push(node.left);
operationStack.push(Operation.PROCESSING);
}
}
return res;
}
}
postorder
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
return modelPost(root);
}
public enum Operation{
PROCESSING,
ADDRESULT
}
public List<Integer> modelPost(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)
return res;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Operation> operationStack = new Stack<>();
nodeStack.push(root);
operationStack.push(Operation.PROCESSING);
while(!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
Operation operation = operationStack.pop();
if(node==null)
continue;
if(operation == Operation.ADDRESULT){
res.add(node.val);
}
else{
nodeStack.push(node);
operationStack.push(Operation.ADDRESULT);
nodeStack.push(node.right);
operationStack.push(Operation.PROCESSING);
nodeStack.push(node.left);
operationStack.push(Operation.PROCESSING);
}
}
return res;
}
public List<Integer> cheatingMethod(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
root = stack.pop();
// res.add(0,root.val);
if (root.left != null) stack.push(root.left );
if (root.right != null) stack.push(root.right);
res.add(root.val);
}
return res;
}
}
114. Flatten Binary Tree to Linked List
class Solution {
public void flatten(TreeNode root) {
// dc(root);
// tvRecursive(root);
tvIterative(root);
}
public void dc(TreeNode root){
if(root==null)
return;
helper(root);
}
public TreeNode helper(TreeNode root){
if(root==null)
return null;
TreeNode leftLeaf = helper(root.left);
TreeNode rightLeaf = helper(root.right);
if(leftLeaf==null && rightLeaf==null)
return root;
if(leftLeaf == null)
return rightLeaf;
leftLeaf.right = root.right;
root.right = root.left;
root.left = null;
if(rightLeaf == null)
return leftLeaf;
return rightLeaf;
}
TreeNode lastNode = null;
public void tvRecursive(TreeNode root){
if(root==null)
return;
if(lastNode!=null){
lastNode.left = null;
lastNode.right = root;
}
TreeNode right = root.right;
lastNode = root;
tvRecursive(root.left);
tvRecursive(right);
}
public void tvIterative(TreeNode root){
if(root==null)
return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node==null)
continue;
if(lastNode!=null){
lastNode.left = null;
lastNode.right = node;
}
TreeNode right = node.right;
lastNode = node;
stack.push(node.right);
stack.push(node.left);
}
}
}
网友评论