企业官网建设流程全解析

微信开发者工具怎么用,南昌百度seo,建设摩托车官方网站,有效果的网站排名找出所有根节点到叶子结点的路径#xff0c;这题比较容易想到的是回溯#xff0c;不过层序遍历用两个队列也可以实现。这里还是只讲回溯回溯版本一#xff1a;递归函数作用#xff1a;处理传入结点的所有子孙结点#xff0c;形成以其左右孩子为起点的到各叶子结点的路径。…找出所有根节点到叶子结点的路径这题比较容易想到的是回溯不过层序遍历用两个队列也可以实现。这里还是只讲回溯回溯版本一递归函数作用处理传入结点的所有子孙结点形成以其左右孩子为起点的到各叶子结点的路径。遍历到叶子结点时组装当前这条路径结果回溯状态path集合递归出口遍历到叶子结点时组装当前这条路径结果第一步根结点加入path第二步将根结点的左孩子结点加入path, 递归处理根结点的左孩子结点处理完后移除path中保存的根结点的左孩子结点此时path中只有根结点第三步将根结点的右孩子结点加入path, 递归处理根结点的右孩子结点处理完后移除path中保存的根结点的右孩子结点此时path中只有根结点class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); //根结点为空直接返回空集合 if (root null) return res; //path用来装某条路径上的所有结点 ListInteger path new ArrayList(); //根结点的值先加入path path.add(root.val); //处理根结点的所有子孙结点加到相应的路径结果中 dfs(root, path, res); // System.out.println(path); return res; } /** *递归函数作用处理传入结点的所有子孙结点形成以其左右孩子为起点的各种到叶子结点的路径。 *遍历到叶子结点时组装当前这条路径结果 */ private void dfs(TreeNode node, ListInteger path, ListString res) { // 如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); return; } //如果存在左孩子结点 if (node.left ! null) { //左孩子结点值加入path path.add(node.left.val); //递归处理左孩子的所有子孙结点 dfs(node.left, path, res); //将path中的左孩子结点值移除 path.remove(path.size() - 1); } //如果存在右孩子结点 if (node.right ! null) { //右孩子结点值加入path path.add(node.right.val); //递归处理右孩子的所有子孙结点 dfs(node.right, path, res); //将path中的右孩子结点值移除 path.remove(path.size() - 1); } } //将path中的结点值拼接成想要的字符串 private String joinPath(ListInteger path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(path.get(i)); } return sb.toString(); } }remove结点版class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); if (root null) return res; ListTreeNode path new ArrayList(); path.add(root); dfs(root, path, res); return res; } private void dfs(TreeNode node, ListTreeNode path, ListString res) { //如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); } else { if (node.left ! null) { path.add(node.left); dfs(node.left, path, res); path.remove(node.left); } if (node.right ! null) { path.add(node.right); dfs(node.right, path, res); path.remove(node.right); } } } private String joinPath(ListTreeNode path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }回溯版本二递归函数作用处理传入结点为根的二叉树所有结点形成传入结点到各叶子结点的路径。遍历到叶子结点时组装当前这条路径结果回溯状态path集合递归出口遍历到叶子结点时组装当前这条路径结果第一步将根结点值加入path第二步递归处理根结点的左子树第三步递归处理根节点的右子树最后移除path中根节点值此时path为空为什么最后要移除path中根节点值以上图中的左子树为例左子树根结点的左右孩子处理完成的时候path中有整颗二叉树的根结点值和其左子树的根结点值接下来该处理整棵二叉树的右子树了因此path中左子树的根结点值需要移除掉。import java.util.*; class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); if (root null) return res; ListInteger path new ArrayList(); dfs(root, path, res); return res; } private void dfs(TreeNode node, ListInteger path, ListString res) { // 1) 记录当前结点到路径 path.add(node.val); // 2) 如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); } else { if (node.left ! null) dfs(node.left, path, res); if (node.right ! null) dfs(node.right, path, res); } // 3) 回溯撤销当前结点 path.remove(path.size() - 1); } private String joinPath(ListInteger path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(path.get(i)); } return sb.toString(); } }remove结点版class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); if (root null) return res; ListTreeNode path new ArrayList(); dfs(root, path, res); return res; } private void dfs(TreeNode node, ListTreeNode path, ListString res) { path.add(node); //如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); } else { if (node.left ! null) { dfs(node.left, path, res); } if (node.right ! null) { dfs(node.right, path, res); } } path.remove(node); } private String joinPath(ListTreeNode path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }回溯版本三这种方式虽然也是对的但是不标准推荐版本一和版本二那种当前层代码移除当前层状态的方式import java.util.*; class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); if (root null) return res; ListInteger path new ArrayList(); dfs(root, path, res); return res; } private void dfs(TreeNode node, ListInteger path, ListString res) { // 1) 记录当前结点到路径 path.add(node.val); // 2) 如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); } else { if (node.left ! null) { dfs(node.left, path, res); //移除的是上面代码调用加入的node.left //属于父结点层移除左孩子 path.remove(path.size() - 1); } if (node.right ! null){ dfs(node.right, path, res); //移除的是上面代码调用加入的node.right //属于父结点层移除右孩子 path.remove(path.size() - 1); } } } private String joinPath(ListInteger path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(path.get(i)); } return sb.toString(); } }remove结点版class Solution { public ListString binaryTreePaths(TreeNode root) { ListString res new ArrayList(); if (root null) return res; ListTreeNode path new ArrayList(); dfs(root, path, res); return res; } private void dfs(TreeNode node, ListTreeNode path, ListString res) { path.add(node); //如果是叶子结点把整条路径拼接成字符串 if (node.left null node.right null) { res.add(joinPath(path)); } else { if (node.left ! null) { dfs(node.left, path, res); path.remove(node.left); } if (node.right ! null) { dfs(node.right, path, res); path.remove(node.right); } } } private String joinPath(ListTreeNode path) { StringBuilder sb new StringBuilder(); for (int i 0; i path.size(); i) { if (i 0) sb.append(-); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }