LeetCode_Input_Helper/treenode_funcs.h at main · SchrodingersCpp/LeetCode_Input_Helper · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#ifndef TREENODE_FUNCS_H
#define TREENODE_FUNCS_H

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "num_string_funcs.h"
#include "treenode.h"

// Finds the longest string value.
std::size_t LongestStrVal(
    const std::vector<std::vector<std::string>>& vec_lvl);

// Formats vector TreeNode string values.
void FormatTreeNodeStrVals(
    std::vector<std::vector<std::string>>& vec_lvl, const std::size_t width);

// Replaces spaces with branch chars.
void GrowInitBranches(std::vector<std::vector<std::string>>& vec_lvl);

// Auxiliary formatting data.
void FormatData(
    std::vector<std::size_t>& dist_to_l_elem,
    std::vector<std::size_t>& dist_btw_elems,
    std::vector<std::size_t>& brch_width,
    const std::vector<std::vector<std::string>>& vec_lvl,
    const std::size_t min_dist);

// Builds a vector with formatted the TreeNode levels.
std::vector<std::string> FormatTreeNodeLvls(
    const std::vector<std::vector<std::string>>& vec_lvl,
    const std::size_t min_dist=1);

// Populates a vector with TreeNode string values.
template <typename T>
void PopulateVectorTree(
    const TreeNode<T>* root,
    std::vector<std::vector<std::string>>& vec_lvl, const int prec=10,
    std::size_t curr_lvl=0, std::size_t curr_idx=0) {
  const std::string str_val{ Number2String(root->val, prec) };
  // Index at level coords.
  std::size_t lvl_curr_idx{
      curr_idx - static_cast<std::size_t>(
          std::pow(2.0, curr_lvl - 1) * 2 - 1) };
  vec_lvl[curr_lvl][lvl_curr_idx] = str_val;
  ++curr_lvl;  // Children are on the next level.
  curr_idx = (curr_idx + 1) * 2 - 1;  // Left child index.
  if (root->left) {
    PopulateVectorTree(root->left, vec_lvl, prec, curr_lvl, curr_idx);
  }
  ++curr_idx;  // Right child index.
  if (root->right) {
    PopulateVectorTree(root->right, vec_lvl, prec, curr_lvl, curr_idx);
  }
}

// Fills a vector containing each levels' formatted string values.
template <typename T>
std::vector<std::vector<std::string>> LevelValues(
    const TreeNode<T>* root, const std::size_t max_depth, const int prec=10) {
  std::vector<std::vector<std::string>> vec_lvl(max_depth);
  for (std::size_t i{}; i < max_depth; ++i) {
    // Number of elements on current level.
    std::size_t n_lvl_elems{ static_cast<std::size_t>(std::pow(2.0, i)) };
    vec_lvl[i] = std::vector<std::string>(n_lvl_elems);
  }
  PopulateVectorTree(root, vec_lvl, prec);
  const std::size_t width{ LongestStrVal(vec_lvl) };
  FormatTreeNodeStrVals(vec_lvl, width);
  return vec_lvl;
}

// Finds TreeNode max depth.
template <typename T>
std::size_t FindTreeNodeMaxDepth(
    const TreeNode<T>* root, const std::size_t curr_d=1, std::size_t max_d=0) {
  max_d = std::max(curr_d, max_d);
  if (root->left) {
    max_d = FindTreeNodeMaxDepth(root->left, curr_d+1, max_d);
  }
  if (root->right) {
    max_d = FindTreeNodeMaxDepth(root->right, curr_d+1, max_d);
  }
  return max_d;
}

// Prints TreeNode.
template <typename T>
void PrintTreeNode(
    const TreeNode<T>* root, const std::size_t min_dist=1, const int prec=10) {
  const std::size_t max_depth{ FindTreeNodeMaxDepth(root) };
  std::vector<std::vector<std::string>> vec_lvl{
      LevelValues(root, max_depth, prec) };
  GrowInitBranches(vec_lvl);
  const std::vector<std::string> vec_fmt_lvl{ FormatTreeNodeLvls(vec_lvl, min_dist) };
  for (const std::string& fmt_lvl : vec_fmt_lvl) {
    std::cout << fmt_lvl << '\n';
  }
}

template <typename T>
void DeleteTreeNode(TreeNode<T>* root) {
  if (root->left) { DeleteTreeNode(root->left); }
  if (root->right) { DeleteTreeNode(root->right); }
  root->left = nullptr;
  root->right = nullptr;
  delete root;
}

#endif  // TREENODE_FUNCS_H