Learn2Live

树相关

10分钟阅读

树相关

打印二叉树最右边的节点

给定一个二叉树，打印其每层最右边的节点的值。

#include <iostream>
#include <vector>
#include <functional>
 
using std::vector;
 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _val):
        val(_val), left(nullptr), right(nullptr) { }
};
 
// print the right-most node of each layer of a tree.
vector<int> PrintRightMost(TreeNode* root)
{
  // - time: O(N), where N is #TreeNodes
  // - space: O(N + logN)
  if (!root) return vector<int>(); 
  vector<vector<int>> mat;
 
  std::function<void(TreeNode*, int)> layer_travel =
    [&mat, &layer_travel](TreeNode* p, int depth)
    {
      if (p == nullptr) return;
      if (depth == (int)mat.size())
        mat.emplace_back(vector<int>());
      mat[depth].push_back(p->val);
      layer_travel(p->left, depth + 1);
      layer_travel(p->right, depth + 1);
    };
 
  vector<int> ret;
  for (auto &row : mat) ret.push_back(row.back());
  return ret;
}

二叉树的层次遍历

给定一颗二叉树，按每一层从左往右的顺序遍历。（队列的典型应用）

/*
 * This is a typical application of queue.
 * With the help of a queue, you can easily do this.
 *
 * You can also use recursion.
 */
 
#include <queue>
#include <vector>
 
using namespace std;
 
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
public:
    vector<int> HierarchicalTraversal(TreeNode* root) {
        if (root == nullptr) { 
            // further error handle
            return vector<int>(); 
        }
 
        vector<int> ret;
        queue<TreeNode*> q;
        q.push(root);
 
        while(!q.empty()) {
            auto cur = q.front();
            // from left to right push the current
            // root's children to the queue
            if (cur -> left) q.push(cur -> left);
            if (cur -> right) q.push(cur -> right);
            ret.push_back(cur -> val);
            q.pop();
        }
        return ret;
    }
 
 
    /// recursive
    vector<vector<int> > layerTraverse(TreeNode* root) {
        if (root == nullptr) return ret;
        build(root, 0); 
        return ret;
    }
 
    // recursion needs a member variable
    vector<vector<int> > ret;
    void build(TreeNode* p, int depth) {
        if (p == nullptr) return;
 
        if (ret.size() == depth)
            ret.push_back(vector<int>());
        ret[depth].push_back(p -> val); // use depth to track layer
        build(p -> left, depth + 1);
        build(p -> right, depth + 1);
    }
};

递增二叉树

网易互娱2020校招正式批

给定一颗二叉树，每个节点又一个正整数权值。若一棵二叉树，每一层的节点权值之和都严格小于下一层的节点权值之和，则称这颗二叉树为递增二叉树。现在给你一颗二叉树，请判断它是否是递增二叉树。

输入描述：

输入的第一行是一个正整数T（0 < T ⇐ 50）。接下来有T组样例，对于每组样例，输入的第一行是一个正整数N，表示树的节点个数（0 < N ⇐ 100，节点编号为0到N-1）。接下来是N行，第k行表示编号为k的节点，输入格式为：VALUE LEFT RIGHT，其中VALUE表示其权值，是一个不超过5000的自然数；LEFT和RIGHT分别表示该节点的左孩子编号和右孩子编号。如果其不存在左孩子或右孩子，则LEFT或RIGHT为-1.

输出描述：

对于每一组样例，输出一个字符串。如果该二叉树是一颗递增树，则输出YES，否则输出NO。

样例输入：

2
8
2 -1 -1
1 5 3
4 -1 6
2 -1 -1
3 0 2
2 4 7
7 -1 -1
2 -1 -1
8
21 6 -1
52 4 -1
80 0 3
31 7 -1
21 -1 -1
59 -1 -1
50 5 -1
48 -1 1

样例输出：

YES
NO

这题最恶心的是输入格式，居然不是直接给一颗建好的二叉树的根节点，而是给数据让你自己建树。处理输入还比较麻烦，首先每个节点都有编号，得先存起来，然后一个一个构造节点，然后再连接起来，关键是连好以后，头节点在哪？还得找一下，最后的判断，实际上是二叉树的层次遍历，遍历得到一个向量，判断是否为严格单调递增即可。

上图是第一个样例画出来的二叉树，左边圆圈中对应的是节点编号，右边的数字是节点的权值。要画这棵树，首先画左边的编号之间的连接图，然后把对应编号换作节点的权值即可。那么头节点在哪呢？入度为0的就是了！

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
 
struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v)
    : val(v), left(nullptr), right(nullptr) {}
};
 
struct NodeInfo
{
  TreeNode* pnode;  
  int left;
  int right;
 
  NodeInfo(TreeNode* p, int l, int r):
    pnode(p), left(l), right(r) {}
};
 
// build the tree and return the root
TreeNode* BuildTree(vector<NodeInfo>& nodes)
{
  vector<int> counts(nodes.size(), 0);
  // link
  for (size_t i = 0; i != nodes.size(); ++i)
  {
    int left = nodes[i].left;
    int right = nodes[i].right;
    if (left != -1)
    {
      nodes[i].pnode->left = nodes[left].pnode;
      ++counts[left];
    }
    if (right != -1)
    {
      nodes[i].pnode->right = nodes[right].pnode;
      ++counts[right];
    }
  }
  // find root
  for (size_t i = 0; i != counts.size(); ++i)
  {
    if (counts[i] == 0)
      return nodes[i].pnode;
  }
  throw std::logic_error("no root");
}
 
// Is the tree a increasing tree?
bool IsIncrTree(TreeNode* root)
{
  if (!root) return false;
  vector<vector<int>> mat; 
 
  // tranverse the tree by layer
  std::function<void(TreeNode*, int)> layer_travel;
  layer_travel = 
    [&mat, &layer_travel](TreeNode* p, int depth) mutable
    {
      if (p == nullptr) return;
      if ((int)mat.size() == depth)
        mat.emplace_back(vector<int>());
        
      mat[depth].push_back(p->val);
      layer_travel(p->left, depth + 1);
      layer_travel(p->right, depth + 1);
    };
 
  layer_travel(root, 0);
  
  vector<int> sums;
  for (auto& row : mat)
  {
    int sum = 0;
    for (auto c : row) sum += c;
    sums.push_back(sum);
  }
 
  for (size_t i = 1; i != sums.size(); ++i)
  {
    if (sums[i-1] >= sums[i])
      return false;
  }
  return true;
}
 
int main()
{
  int num_test;
  cin >> num_test;
  
  for (int num_nodes = 0; num_test--;)
  {
    cin >> num_nodes;
    vector<NodeInfo> nodes;
    while (num_nodes--)
    {
      int v, l, r;
      cin >> v >> l >> r;
      TreeNode* p = new TreeNode(v);
      nodes.emplace_back(p, l, r);
    }
    TreeNode* root = BuildTree(nodes);
    if (IsIncrTree(root))
      cout << "YES\n";
    else
      cout << "NO\n";
 
    // memory clean
    for (auto& node : nodes)
    {
      delete node.pnode;
      node.pnode = nullptr;
    }
  } // nodes released
  return 0;
}

题九：Stern-Brocot Tree

网易雷火游戏2019校招

The Stern-Brocot tree is an infinite complete binary tree in which the verices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.

Stern-Brocot Tree

Figure above shows a part of the Stern-Brocot tree, which has the first 4 rows. The value in the node is the mediant of the left and right fractions. The mediant of two fractions A/B and C/D is defined as (A+C)/(B+D).

To construct the Stern-Brocot tree, we first define the left fraction of the root node is 0/1, and the right fraction of the root node is 1/0. So the value in the root node is the mediant of 0/1 and 1/0, which is (0+1)/(1+0)=1/1. Then the value of root node becomes the right fraction of the left child, and the left fraction of the right child. For example, the 1st node in row2 has 0/1 as its left fraction and 1/1(which is the value of its parent node) as its right fraction. So the value of the 1st node on row2 is (0+1)(1+1)=1/2. For the same reason, the value of the 2nd node in row2 is (1+1)/(1+0)=2/1. This construction progress goes on infinity. As a result, every positive rational number can be found on the Stern-Brocot tree, and can be found only once.

Give a rational nunmber in form P/Q, find the position of P/Q in the Stern-Borcot tree.

Input description: Input consists of two integers, P and Q (1⇐P,Q ⇐ 1000), which represent the rational number P/Q. We promise P and Q are relatively prime.

Output description: Output consists of two integers, R and C. R indicates the row index of P/Q in the Stern-Brocot tree, C indicates the index of P/Q in that row. Both R and C are base 1. We promise the position of P/Q is always in the first 12 rows of the Stern-Brocot tree, which means R⇐12.

Sample input:

5 3

Sample output:

4 6

Idea: tree structure is natural for recursion.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
 
using namespace std;
 
// build Rat abstraction
typedef std::pair<int, int> Rat;  // the rational numbers
 
Rat operator+(const Rat& lhs, const Rat& rhs)
{
  // 事实上这里需要化简使得分子分母互素
  // 不过下面我判断等于的时候是交叉相乘判断的，故不影响结果
  return std::make_pair(
      lhs.first + rhs.first,
      lhs.second + rhs.second);
}
 
bool operator<(const Rat& lhs, const Rat& rhs)
{
  return (lhs.first * rhs.second)
       < (rhs.first * lhs.second);
}
 
bool operator>(const Rat& lhs, const Rat& rhs)
{
  return !(lhs < rhs);
}
 
bool operator==(const Rat& lhs, const Rat& rhs)
{
  return (lhs.first * rhs.second)
      == (rhs.first * lhs.second);
}
 
void Printer(const Rat& r)
{
  cout << r.first << "/" << r.second << endl;
}
// done
 
struct SBTreeNode
{
  Rat LF; // left fraction
  Rat val;
  Rat RF; // right fraction
  SBTreeNode(Rat l, Rat v, Rat r)
    : LF(l), val(v), RF(r)
  {
  }
};
 
/// search the SBTree for target, return the row and col index
void SearchOnTree(
    SBTreeNode& root, const Rat& target, int* prow, int* pcol)
{
  // base case
  if (target == root.val) return;
  
  // 可以看到Stern-Brocot树具有二叉排序树的特征
  // left-child < parent < right-child
  if (target < root.val)
  { // go left
    root.RF = root.val;
    root.val = root.val + root.LF;
    ++(*prow);
    *pcol = (*pcol) * 2 - 1;
    SearchOnTree(root, target, prow, pcol);
  }
  else if (target > root.val)
  { // go right
    root.LF = root.val;
    root.val = root.val + root.RF;
    ++(*prow);
    (*pcol) *= 2; // 注意列索引的增量，仔细看规律
    SearchOnTree(root, target, prow, pcol);
  }
}
 
int main()
{
  Rat query;
  cin >> query.first >> query.second;
  SBTreeNode root(Rat(0,1), Rat(1,1), Rat(1,0));
  // root.RF = root.val;
  // root.val = root.val + root.LF;
  // cout << "LF "; Printer(root.LF);
  // cout << "val "; Printer(root.val);
  // cout << "RF "; Printer(root.RF);
 
  int row = 1, col = 1;
  SearchOnTree(root, query, &row, &col);
  cout << row << " " << col << endl;
  return 0;
}

关系图谱

反向链接