C++ 中的二叉树倒置
c++server side programmingprogramming
假设我们有一棵二叉树,其中所有右节点要么是具有兄弟节点的叶节点,要么为空,我们必须将其倒置并将其变成一棵树,其中原来的右节点变为左叶节点。我们必须返回新节点。
因此,如果输入为 [1,2,3,4,5]
然后输出将返回二叉树的根 [4,5,2,#,#,3,1]
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数解决(),这将采用节点、par、兄弟节点,
如果节点不存在,则 −
返回 NULL
child = 节点左侧
currSib = 节点右侧
节点 := 兄弟节点左侧
节点 := par 右侧
如果 child 和 currSib 不存在,则 −
return node
return solve(child, node, currSib)
从 main 方法执行以下操作 −
return solve(root, NULL, NULL)
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue 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; } void inord(TreeNode *root){ if(root != NULL){ inord(root->left); cout << root->val << " "; inord(root->right); } } class Solution { public: TreeNode* solve(TreeNode* node, TreeNode* par, TreeNode* sibling){ if (!node || node->val == 0) return NULL; TreeNode* child = node->left; TreeNode* currSib = node->right; node->left = sibling; node->right = par; if (!child && !currSib) return node; return solve(child, node, currSib); } TreeNode* upsideDownBinaryTree(TreeNode* root) { return solve(root, NULL, NULL); } }; main(){ Solution ob; vector<int< v = {1,2,3,4,5}; TreeNode *root = make_tree(v); inord(ob.upsideDownBinaryTree(root)); }
输入
[1,2,3,4,5]
输出
[4,5,2,null,null,3,1]