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 kthSmallest(TreeNode root, int k) {
          Map<TreeNode, Integer> counts = new HashMap<>();
          calculateCounts(root, counts);
          return quickSelectOnTree(root, k, counts);
      }
      private int calculateCounts(TreeNode root, Map<TreeNode, Integer> counts) {
          if (root == null) {
              counts.put(root, 0);
              return 0;
          }
          int left = calculateCounts(root.left, counts);
          int right = calculateCounts(root.right, counts);
          counts.put(root, left + right + 1);
          return left + right + 1;
      }
      private int quickSelectOnTree(TreeNode root, int k, Map<TreeNode, Integer> counts) {
          if (root == null) {
              return -1;
          }
          int left = counts.get(root.left);
          if (left >= k) {
              return quickSelectOnTree(root.left, k, counts);
          }
          if (left + 1 == k) {
              return root.val;
          }
          return quickSelectOnTree(root.right, k - left - 1, counts);
      }
    }

3. Non-recursive traversal

  • 非递归的遍历树，如果栈不为空，且循环到了第k个点，那么就直接返回stack.peek()，否则返回-1
  • 时间复杂度O(n)
    public class Solution {
      public int kthSmallest(TreeNode root, int k) {
          if (root == null) {
              return -1;
          }
          TreeNode dummy = new TreeNode(-1);
          dummy.right = root;
          Stack<TreeNode> stack = new Stack<TreeNode>();
          stack.push(dummy);
          for (int i = 0; i < k && !stack.isEmpty(); i++) {
              TreeNode head = stack.pop();
              if (head.right != null) {
                  head = head.right;
                  while (head != null) {
                      stack.push(head);
                      head = head.left;
                  }
              }
          }
          return stack.peek() != null ? stack.peek().val: -1;
      }
    }

4. BST iterator traversal

  • 非递归的遍历树，如果栈不为空，且循环到了第k个点，那么就直接返回stack.peek()，否则返回-1
  • 时间复杂度O(n)
    public class Solution {
      public int kthSmallest(TreeNode root, int k) {
          if (root == null) {
              return -1;
          }
          Stack<TreeNode> stack = new Stack<>();
          while (root != null) {
              stack.push(root);
              root = root.left;
          }
          for (int i = 0; i < k - 1; i++) {
              next(stack);
          }
          return hasNext(stack) ? stack.peek().val: -1;
      }
      private boolean hasNext(Stack<TreeNode> stack) {
          return !stack.isEmpty();
      }
      private TreeNode next(Stack<TreeNode> stack) {
          TreeNode head = stack.peek();
          if (head.right == null) {
              head = stack.pop();
              while (!stack.isEmpty() && stack.peek().right == head) {
                  head = stack.pop();
              }
          } else {
              head = head.right;
              while (head != null) {
                  stack.push(head);
                  head = head.left;
              }
          }
          return stack.peek();
      }
    }

Tree上的DFS求所有根到叶子结点的路径

1. Traverse

  • 先判断是否为空，为空就返回
  • 判断当左右节点均为空的时候，此时只有根节点，把根节点加入sb，然后sb加入results
  • 左节点不为空，把根节点加入sb，dfs左节点，把根节点从sb中删除
  • 有节点不为空，把根节点加入sb，dfs右节点，把根节点从sb中删除
  • 注意如果使用StringBuilder的话，记录下len，每次删除的时候就sb.delete(len, sb.length());
    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
      public List<String> binaryTreePaths(TreeNode root) {
          List<String> results = new ArrayList<>();
          if (root == null) {
              return results;
          }
          dfs(root, new StringBuilder(), results);
          return results;
      }
      private void dfs(TreeNode root, StringBuilder sb, List<String> results) {
          if (root == null) {
              return;
          }
          int len = sb.length();
          if (root.left == null && root.right == null) {
              sb.append(root.val);
              results.add(sb.toString());
              sb.delete(len, sb.length());
              return;
          }
          if (root.left != null) {
              sb.append(root.val);
              sb.append("->");
              dfs(root.left, sb, results);
              sb.delete(len, sb.length());
          }
          if (root.right != null) {
              sb.append(root.val);
              sb.append("->");
              dfs(root.right, sb, results);
              sb.delete(len, sb.length());
          }
      }
    }

2. DivideConquer

  • 先创建此层需要返回的子结果集
  • 无脑递归左节点和有节点
  • 判断当左右节点的子结果集均为空的时候，此时只有根节点，把根节点加入当前子结果集，返回
  • 左节点不为空，左节点子结果集循环加入当前子结果集中
  • 有节点不为空，右节点子结果集循环加入当前子结果集中
  • 返回当前子结果集
    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
      public List<String> binaryTreePaths(TreeNode root) {
          // write your code here
          return dfs(root);
      }
      private List<String> dfs(TreeNode root) {
          List<String> result = new ArrayList<>();
          if (root == null) {
              return result;
          }
          List<String> leftResult = dfs(root.left);
          List<String> rightResult = dfs(root.right);
          if ((leftResult == null || leftResult.size() == 0) && (rightResult == null || rightResult.size() == 0)) {
              result.add(String.valueOf(root.val));
              return result;
          }
          if (leftResult != null && leftResult.size() > 0) {
              for (String item: leftResult) {
                  result.add(root.val + "->" + item);
              }
          }
          if (rightResult != null && rightResult.size() > 0) {
              for (String item: rightResult) {
                  result.add(root.val + "->" + item);
              }
          }
          return result;
      }
    }

Invert Tree的多种方法

1. Recursion

  • root为left被invert之后的node和right被invert之后的node交换得来
    public class Solution {
      public void invertBinaryTree(TreeNode root) {
          invertTree(root);
      }
      private TreeNode invertTree(TreeNode root) {
          if (root == null) {
              return null;
          }
          TreeNode left = invertTree(root.left);
          TreeNode right = invertTree(root.right);
          root.left = right;
          root.right = left;
          return root;
      }
    }

2. BFS

  • 使用BFS的层级遍历，把每一层的左右两节点交换
    public class Solution {
      public void invertBinaryTree(TreeNode root) {
          if(root == null) {
              return;
          }
          Queue<TreeNode> queue = new LinkedList<>();
          queue.offer(root);
          while (!queue.isEmpty()) {
              TreeNode head = queue.poll();
              TreeNode temp = head.left;
              head.left = head.right;
              head.right = temp;
              if (head.left != null) {
                  queue.offer(head.left);
              }
              if (head.right != null) {
                  queue.offer(head.right);
              }
          }
      }
    }

3. DFS

  • 和BFS唯一的区别就是使用stack而不是queue
    public class Solution {
      public void invertBinaryTree(TreeNode root) {
          if (root == null) {
              return;
          }
          Stack<TreeNode> stack = new Stack<>();
          stack.push(root);
          while(!stack.isEmpty()) {
              TreeNode head = stack.pop();
              TreeNode temp = head.left;
              head.left = head.right;
              head.right = temp;
              if(head.left != null) {
                  stack.push(head.left);
              }
              if(head.right != null) {
                  stack.push(head.right);
              }
          }
      }
    }

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 DFS

-
Tree DFS Tree DFS Tree上的DFS分为两种（Divide Conquer + Traversal和纯Divide Conquer） 建立当前/用全局变量（根据不同的方式） root 为 空 （ 返回 什么/ 更新 指针） 左 节点和 右 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） 左 节点和 右 节点 不 为 空 ，用 左右 构建 当前 解 返回 当前 /选择 左 ， 右 ， 中 Divide Conquer + Traversal 不同 一般 没有 全局变量， 创建当前 变量作为当前最终解 通过 左 节点的最终解和 右 节点的最终解， 计算 并更新 当前 变量 判断 左 节点的最终解， 右 节点的最终解， 当前 变量，在三个解中 选择 一个 作为当前层的最终解 返回 更新传入的参数指针 （ 有时会单独建立 class Result 类 ） 流程 建立 当前 变量（不一定第一步） root 为 空 （ 返回 什么） left 节点和 right 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） left 节点和 right 节点 不 为 空 ，用 左右 解 leftResult , rightResult 计算 当前 解 选择 符合的解 比较 （ leftResult ， rightResult ， result ） + 选出 合适的解 直接使用 ：当前解 使用 选中的解 返回 更新 传入的指针 例题（Minimum Subtree） public class Solution { class Result { TreeNode minSubtree; int minSum; int sum; Result(TreeNode minSubtree, int minSum, int sum) { this.minSubtree = minSubtree; this...
Read more