C++二叉树边界

假设我们有一个二叉树，我们需要找到其边界值，方向为逆时针方向，从根节点开始。边界包括左边界、叶子节点和右边界，按顺序排列，不包含重复节点。

• 左边界是从根节点到最左节点的路径。

• 右边界是从根节点到最右节点的路径。

• 当根节点没有左子树或右子树时，根节点本身就是左边界或右边界。

所以，如果输入如下：

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

为了解决这个问题，我们将遵循以下步骤：

• 定义一个数组 ret

• 定义一个函数 leftBoundary()，它将接收一个节点作为参数：

• 如果节点为空或节点是叶子节点，则：

  • 返回

• 将节点的值插入 ret 中

• 如果节点的左子节点存在，则：

  • leftBoundary(节点的左子节点)

• 否则

  • leftBoundary(节点的右子节点)

• 定义一个函数 rightBoundary()，它将接收一个节点作为参数：

• 如果节点为空或节点是叶子节点，则：

  • 返回

• 将节点的值插入 ret 中

• 如果节点的右子节点存在，则：

  • rightBoundary(节点的左子节点)

• 否则

  • rightBoundary(节点的右子节点)

• 定义一个函数 leaves()，它将接收一个节点作为参数：

• 如果节点不存在，则返回

  • 返回

• 如果节点是叶子节点，则：

  • 将节点的值插入 ret 中

• leaves(节点的左子节点)

• leaves(节点的右子节点)

• 在主方法中执行以下操作：

• 清空 ret 数组

• 如果根节点不存在，则：

  • 返回 ret

• 将根节点的值插入 ret 中

• leftBoundary(根节点的左子节点)

• leaves(根节点的左子节点);

• leaves(根节点的右子节点);

• rightBoundary(根节点的右子节点)

• 返回 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));
}

输入

{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}

输出

[1, 2, 4, 7, 8, 9, 10, 6, 3, ]

Arnab Chakraborty

更新于：2020-11-16

浏览量：157

开启你的职业生涯

完成课程获得认证

开始学习