商城推广方案_网站建设建站公司_win7优化工具哪个好用_商业网站

目录

计算布尔二叉树的值

求根节点到叶节点数字之和（稍困难）

二叉树剪枝

验证二叉搜索树

二叉搜索树中第 K 小的元素

二叉树的所有路径

全排列

子集

---

深度优先遍历（DFS），是我们树或者图这样的数据结构中常用的一种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到一条路径上的所有结点都能被遍历完毕，然后回溯到上一层，继续找一条路遍历。

在二叉树中，常见的深度优先遍历为：前序遍历、中序遍历、后序遍历

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅易理解而且代码简洁，并且前中后序三种遍历的唯一区别就是访问根节点的时机不同。

遍历是形式，目的是搜索。回溯与剪枝 本质就是深搜

计算布尔二叉树的值

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

解法：递归

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean evaluateTree(TreeNode root) {if (root.left == null)return root.val == 0 ? false : true;boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left | right : left & right;// 逻辑与 逻辑或}
}

求根节点到叶节点数字之和（稍困难）

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

解法：递归

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int preSum) {preSum = preSum * 10 + root.val;if (root.left == null && root.right == null) {return preSum;}int ret = 0;if (root.left != null)ret += dfs(root.left, preSum);if (root.right != null)ret += dfs(root.right, preSum);return ret;}
}

二叉树剪枝

814. 二叉树剪枝 - 力扣（LeetCode）

解法：通过决策树，抽象出递归的三个核心问题

后序遍历

1. 函数头 Node* dfs( root )
2. 函数体 
   1. 处理左子树
   2. 处理右子树
   3. 判断
3. 递归出口 root==null,return null;

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode pruneTree(TreeNode root) {if (root == null)return root;root.left = pruneTree(root.left);root.right = pruneTree(root.right);if (root.left == null && root.right == null && root.val == 0)root = null;return root;}
}

验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

二叉搜索树的中序遍历，是一个有序的序列

1. 全局变量的优势
2. 回溯
3. 剪枝（加快搜索过程）

策略一：左子树是二叉搜索树；当前节点符合二叉搜索树的定义；右子树也是二叉搜索树

策略二：剪枝

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null)return true;boolean left = isValidBST(root.left);// 左if (left == false)return false;// 剪枝boolean cur = false;if (root.val > prev)cur = true;// 中if (cur == false)return false;// 剪枝prev = root.val;boolean right = isValidBST(root.right);// 右return left && cur && right;}
}

二叉搜索树中第 K 小的元素

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

解法：两个全局变量＋中序遍历（有序）+剪枝优化

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {int count = 0;int ret = 0;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}void dfs(TreeNode root) {if (root == null || count == 0)return;// 判空+剪枝（count=0时直接返回）// 中序遍历dfs(root.left);// 左count--;if (count == 0) {// 中ret = root.val;return;}dfs(root.right);// 右}
}

二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

全局变量

回溯->“恢复现场”

剪枝

函数头：void dfs(root,path)

函数体：if(root==叶)：；root≠叶：；

递归出口：if(root==null) return;

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer());return ret;}void dfs(TreeNode root, StringBuffer _path) {StringBuffer path = new StringBuffer(_path);path.append(Integer.toString(root.val));if (root.left == null && root.right == null) {// 根节点ret.add(path.toString());// 返回该路径，给retreturn;}path.append("->");if (root.left != null)dfs(root.left, path);// 剪枝if (root.right != null)dfs(root.right, path);// 剪枝}
}

全排列

46. 全排列 - 力扣（LeetCode）

解法：穷举（枚举）+  递归

1. 画出决策树：越详细越好
2. 设计代码
   1. 全局变量 int[][] ret; int[] path; bool[] check;(实现剪枝)
   2. dfs函数 - 仅需关心某个节点在干什么
   3. 细节：回溯（干掉path最后一个元素；修改check数组）

class Solution {// 设置全局变量List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums) {if (path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (check[i] == false) {path.add(nums[i]);check[i] = true;dfs(nums);// 回溯-恢复现场check[i] = false;path.remove(path.size() - 1);}}}
}

子集

78. 子集 - 力扣（LeetCode）

​

叶节点即结果

1. 决策树
2. 设计代码
   1. 全局变量 int[ ] path; int[ ] ret;
   2. dfs(nums,i)
      1. 选：path+=nums[ i ],dfs(nums,i+1)
      2. 不选：dfs(nums,i+1)

细节：剪枝，回溯，递归出口

class Solution {// 设置全局变量List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {ret.add(new ArrayList<>(path));for (int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);// 回溯-恢复现场}}
}