C++ 中二叉树的边界

c++server side programmingprogramming

假设我们有一棵二叉树，我们必须从根开始逆时针方向找到其边界的值。这里的边界包括左边界、叶子和右边界，顺序不重复。

左边界是从根到最左边节点的路径。
右边界是从根到最右边节点的路径。
当根没有左子树或右子树时，根本身就是左边界或右边界。

所以，如果输入是这样的

那么输出将是 [1,2,4,7,8,9,10,6,3]

要解决为此，我们将遵循以下步骤 −

定义一个数组 ret
定义一个函数 leftBoundary()，它将获取节点，
如果节点为空或节点为叶，则 −
- return
将节点的值插入到 ret 中
如果节点的左侧存在，则 −
- leftBoundary(left of node)
Otherwise
- leftBoundary(right of node)
定义一个函数 rightBoundary()，它将接受节点，
如果节点为空或节点为叶，则 −
- return
将节点的值插入到 ret 中
如果节点的右侧存在，则 −
- rightBoundary(left of node)
否则
- rightBoundary(right of node)
定义一个函数 leaves()，它将获取节点，
如果节点不存在，则 −
- return
如果节点是叶子，则 −
- 将节点的 val 插入到 ret 中
leaves(left of node)
leaves(right of node)
从 main 方法执行以下操作 −
清除 ret 数组
如果 root 不存在，则 −
- return ret
将 root 的 val 插入到 ret 中
leftBoundary(left of root)
leaves(left of root);
leaves(right of root);
rightBoundary(right of root)
return ret

示例

让我们看下面的实现，以便更好地理解 −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   vector<int> ret;
   void leftBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      ret.push_back(node->val);
      if (node->left && node->left->val != 0)
         leftBoundary(node->left);
      else
         leftBoundary(node->right);
   }
   void rightBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      if (node->right && node->right->val != 0) {
         rightBoundary(node->right);
      }
      else {
         rightBoundary(node->left);
      }
      ret.push_back(node->val);
   }
   void leaves(TreeNode* node){
      if (!node || node->val == 0)
         return;
      if (!node->left && !node->right) {
         ret.push_back(node->val);
      }
      leaves(node->left);
      leaves(node->right);
   }
   vector<int> boundaryOfBinaryTree(TreeNode* root){
      ret.clear();
      if (!root)
         return ret;
      ret.push_back(root->val);
      leftBoundary(root->left);
      leaves(root->left);
      leaves(root->right);
      rightBoundary(root->right);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
   TreeNode *root = make_tree(v);
   print_vector(ob.boundaryOfBinaryTree(root));
}