Tree DFS

-
Tree DFS

Tree DFS

Tree上的DFS分为两种（Divide Conquer + Traversal和纯Divide Conquer）

  • 建立当前/用全局变量（根据不同的方式）
  • root为空（返回什么/更新指针）
  • 左节点和右节点都为空，用root构建当前解（返回什么/更新指针）
  • 左节点和右节点不为空，用左右构建当前解
  • 返回当前/选择左，右，中

Divide Conquer + Traversal

  1. 不同

    • 一般没有全局变量，创建当前变量作为当前最终解
    • 通过左节点的最终解和右节点的最终解，计算并更新当前变量
    • 判断左节点的最终解，右节点的最终解，当前变量，在三个解中选择一个
    • 作为当前层的最终解
      • 返回
      • 更新传入的参数指针
    • （有时会单独建立class Result类）

  2. 流程

    • 建立当前变量（不一定第一步）
    • root为空（返回什么）
    • left节点和right节点都为空，用root构建当前解（返回什么/更新指针）
    • left节点和right节点不为空，用左右解leftResult, rightResult计算当前解
    • 选择符合的解
      • 比较 （leftResult，rightResult，result）+ 选出合适的解
      • 直接使用：当前解
    • 使用选中的解
      • 返回
      • 更新传入的指针

  3. 例题（Minimum Subtree）

    public class Solution {
     class Result {
         TreeNode minSubtree;
         int minSum;
         int sum;
         Result(TreeNode minSubtree, int minSum, int sum) {
             this.minSubtree = minSubtree;
             this.minSum = minSum;
             this.sum = sum;
         }
     }
     public TreeNode findSubtree(TreeNode root) {
         return dfs(root).minSubtree;
     }
     private Result dfs(TreeNode root) {
         if (root == null) {
             return new Result(root, Integer.MAX_VALUE, 0);
         }
         Result left = dfs(root.left);
         Result right = dfs(root.right);
         if (left.minSubtree == null && right.minSubtree == null) {
             return new Result(root, Integer.MAX_VALUE, root.val);
         }
         int currSum = left.sum + right.sum + root.val;
         Result curr = new Result(root, currSum, currSum);
         if (left.minSubtree != null) {
             if (left.minSum <= curr.minSum) {
                 curr.minSubtree = left.minSubtree;
                 curr.minSum = left.minSum;
             }
         }
         if (right.minSubtree != null) {
             if (right.minSum <= curr.minSum) {
                 curr.minSubtree = right.minSubtree;
                 curr.minSum = right.minSum;
             }
         }
         return curr;
     }
    }

  4. 例题（Binary Tree Paths）

    • 直接返回最终解

      public class Solution {
         public List<String> binaryTreePaths(TreeNode root) {
           return dfs(root, new StringBuilder());
         }
         private List<String> dfs(TreeNode root, StringBuilder sb) {
             List<String> result = new ArrayList<>();
             if (root == null) {
                 return result;
             }
             if ((root.left == null) && (root.right == null)) {
                 sb.append(String.valueOf(root.val));
                 result.add(sb.toString());
                 return result;
             }
             int index = sb.length();
             if (root.left != null) {
                 sb.append(root.val + "->");
                 List<String> leftResult = dfs(root.left, sb);
                 sb.delete(index, sb.length());
                 for (String item: leftResult) {
                     result.add(item);
                 }
             }
             if (root.right != null) {
                 sb.append(root.val + "->");
                 List<String> rightResult = dfs(root.right, sb);
                 sb.delete(index, sb.length());
                 for (String item: rightResult) {
                     result.add(item);
                 }
             }
             return result;
         }
      }

    • 更新全局变量

      public class Solution {
      public List<String> binaryTreePaths(TreeNode root) {
         List<String> result = new ArrayList<>();
         dfs(root, new StringBuilder(), result);
         return result;
      }
      private void dfs(TreeNode root, StringBuilder sb, List<String> result) {
         if (root == null) {
             return;
         }
         if (root != null && root.left == null && root.right == null) {
             sb.append(String.valueOf(root.val));
             result.add(sb.toString());
             return;
         }
         int index = sb.length();
         if (root.left != null) {
             sb.append(root.val + "->");
             dfs(root.left, sb, result);
             sb.delete(index, sb.length());
         }
         if (root.right != null) {
             sb.append(root.val + "->");
             dfs(root.right, sb, result);
             sb.delete(index, sb.length());
         }
      }
      }

Divide Conquer

  1. 不同

    • 一般有全局变量，直接返回/打擂台
    • 最终解作为最终返回值
    • 通过左节点的最终解和右节点的最终解，更新当前最终解
    • 当前最终解作为全局最终解直接返回

  2. 流程

    • root为空（返回什么）
    • 左节点和右节点都为空，用root构建当前解（返回什么）
    • 左节点和右节点不为空，用左右构建当前解
    • 使用当前最终解返回

  3. 例题（Minimum Subtree）

    public class Solution {
     private TreeNode minSubtree;
     private int minSum;
     public TreeNode findSubtree(TreeNode root) {
         // 这里minSum不能设为root.val
         // 如果最初是root是最小子树，应该设置成root.val + leftSum + rightSum
         // 但是此时我们不知道leftSum和rightSum，所以就默认leftSum和rightSum是Integer.MAX_VALUE
         // 加在一起为了不溢出，就直接设置成Integer.MAX_VALUE
         this.minSum = Integer.MAX_VALUE;
         this.minSubtree = root;
         dfs(root);
         return this.minSubtree;
     }
     private int dfs(TreeNode root) {
         if (root == null) {
             return 0;
         }
         int leftSum = dfs(root.left);
         int rightSum = dfs(root.right);
         if (leftSum == 0 && rightSum == 0) {
             if (root.val <= minSum) {
                 minSubtree = root;
                 minSum = root.val;
             }
             return root.val;
         }
         int sum = leftSum + rightSum + root.val;
         if (sum <= minSum) {
             minSubtree = root;
             minSum = sum;
         }
         return sum;
     }
    }

  4. 例题（Binary Tree Paths）

    • 左右结果构建当前解，直接返回当前解给上一层
      public class Solution {
         public List<String> binaryTreePaths(TreeNode root) {
          List<String> result = new ArrayList<>();
          if (root == null) {
              return result;
          }
          List<String> leftList = binaryTreePaths(root.left);
          List<String> rightList = binaryTreePaths(root.right);
          if ((leftList == null || leftList.size() == 0) && (rightList == null || rightList.size() == 0)) {
              result.add(String.valueOf(root.val));
              return result;
          }
          if (leftList != null && leftList.size() > 0) {
              for (String item: leftList) {
                  result.add(root.val + "->" + item);
              }
          }
          if (rightList != null && rightList.size() > 0) {
              for (String item: rightList) {
                  result.add(root.val + "->" + item);
              }
          }
          return result;
        }
      }

Comments

Post a Comment

Popular posts from this blog

Union Find 模板

-
Union Find Union Find Union Find 动态的计算联通块问题 结构 global variables constructor() find(int x) union(int a, int b) 模板 (Map) global variables private Map<Integer, Integer> f; constructor() UnionFind(int n) { this.f = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { f.put(i, i); } } find(int x) int find(int x) { int root = x; // 找到“根” while (f.get(root) != root) { root = f.get(root); } // 拆“整”为“零”，把每个元素直接接到“根”上 while (root != x) { int nx = f.get(x); f.put(x, root); x = nx; } return root; } union(int a, int b) void union(int a, int b) { int rA = find(a); int rB = find(b); if (rA != rB) { f.put(rB, rA); } } 例题 Friend Circles 根据模板添加额外的全局变量，比如此题需要count，在每次合并的时候 count-- ，在初始化的时候或者写一个 setter 和 getter 去给 count 赋值和取值 public class Solution { class UnionFind { private int count; private Map...
Read more

Tree的经典题

-
Tree的经典题 Tree的经典题 找第k小 Kth Smallest Element in a BST 在树上就不需要使用Heap了，因为inorder traversal本身就是一个从小到大的序列，这里我们有几种方法 1. Recursive traversal 创建全局变量，记录traverse到哪儿了，当走到k的时候把值赋给result即可 时间复杂度 O(n) public class Solution { //设置全局变量 private int count = 0; private int result = 0; public int kthSmallest(TreeNode root, int k) { traversal(root, k); return result; } private void traversal(TreeNode root, int k) { if (root == null) { return; } traversal(root.left, k); //如果count等于k的时候才把结果赋给result //注意count从0开始，所以count先++之后再判断 count++; if (count == k) { result = root.val; } traversal(root.right, k); } } 2. Quick Select on Tree 首先要traverse计算每个点到它的时候子树总共有多少个点，然后用quick select，如果大于k，直接去左边找，如果小于k，判断当左边的个数加1正好等于k，那么这个k就落在root上，如果加1之后还小于k那么就要去向右边找了，因为此时左边没有第k个点。 时间复杂度 O(n) 最好最坏都是 public class Solution { public int kthSmal...
Read more