- Single valued binary tree
If each node of a binary tree has the same value, the binary tree is a single valued binary tree.
true is returned only when the given tree is a single valued binary tree; Otherwise, false is returned.
Example 1:
Input: [1,1,1,1, null, 1]
Output: true
Example 2:
Input: [2,2,2,5,2]
Output: false
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isUnivalTreeHelp(TreeNode * root, int val)
{
if (!root)
return true;
return root->val == val &&
isUnivalTreeHelp(root->left, val) &&
isUnivalTreeHelp(root->right, val);
}
bool isUnivalTree(TreeNode* root) {
if (!(root->left) && !(root->right))
return true;
int value = root->val;
return isUnivalTreeHelp(root, value);
}
};
- Maximum depth of binary tree
Given a binary tree, find its maximum depth.
The depth of the binary tree is the number of nodes on the longest path from the root node to the farthest leaf node.
Note: leaf nodes refer to nodes without child nodes.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
Returns its maximum depth 3.
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)
return 0;
if (!(root->left) && !(root->right))
return 1;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
- Flip binary tree
Flip a binary tree.
Example:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void invertTreeHeaper(TreeNode * root)
{
if (!root) //Must have
return;
if (!(root->left) && !(root->right))
return;
//Treatment root
TreeNode * tmp = root->left;
root->left = root->right;
root->right = tmp;
invertTreeHeaper(root->left);
invertTreeHeaper(root->right);
}
TreeNode* invertTree(TreeNode* root) {
if (!root)
return NULL;
if (!(root->left) && !(root->right))
return root;
invertTreeHeaper(root);
return root;
}
};
- Same tree
Give you the root nodes p and q of two binary trees and write a function to check whether the two trees are the same.
If two trees are structurally identical and the nodes have the same value, they are considered to be the same.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q)
return true;
if (!p || !q)
return false;
return p->val == q->val &&
isSameTree(p->left, q->left)&&
isSameTree(p->right, q->right);
}
};
- Symmetric binary tree
Given a binary tree, check whether it is mirror symmetric.
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetricHelper(TreeNode * root1, TreeNode * root2)
{
if (!root1 && !root2)
return true;
if (!root1 || !root2)
return false;
return root1->val == root2->val &&
isSymmetricHelper(root1->left, root2->right)&&
isSymmetricHelper(root1->right, root2->left);
}
bool isSymmetric(TreeNode* root) {
if (!root)
return true;
if (!(root->left) && !(root->right))
return true;
TreeNode * tmp = root;
return isSymmetricHelper(root, tmp);
}
};
- Preorder traversal of binary tree
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void preorderTraversalHeaper(TreeNode * root, vector<int> & res)
{
if (!root)
return ;
res.push_back(root->val);
preorderTraversalHeaper(root->left, res);
preorderTraversalHeaper(root->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
if (!root)
return {};
vector<int> res;
preorderTraversalHeaper(root, res);
return res;
}
};
- Middle order traversal of binary tree
Given the root node of a binary tree, root, returns its middle order traversal.
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorderTraversalHeaper(TreeNode * root, vector<int> & res)
{
if (!root)
return;
inorderTraversalHeaper(root->left, res);
res.push_back(root->val);
inorderTraversalHeaper(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
if (!root)
return {};
vector<int> res;
inorderTraversalHeaper(root, res);
return res;
}
};
- Binary Tree Postorder Traversal
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void postorderTraversalHelper(TreeNode * root, vector<int> & res)
{
if (!root)
return;
postorderTraversalHelper(root->left, res);
postorderTraversalHelper(root->right, res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
if (!root)
return {};
vector<int> res;
postorderTraversalHelper(root, res);
return res;
}
};
- Sequence traversal of binary tree
To give you a binary tree, please return the node values obtained by traversing in sequence. (that is, access all nodes from left to right layer by layer).
Example:
Binary tree: [3,9,20,null,null,15,7],
3
9 20
15 7
Return its sequence traversal result:
[
[3],
[9,20],
[15,7]
]
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root)
return {};
queue<TreeNode*> qu;
vector< vector<int> > result;
qu.push(root);
while (!qu.empty())
{
vector<int> v;
int size = qu.size();
for (int i = 0; i < size; i++)
{
TreeNode * node = qu.front();
v.push_back(node->val);
qu.pop();
if (node->left)
qu.push(node->left);
if (node->right)
qu.push(node->right);
}
result.push_back(v);
}
return result;
}
};
- A subtree of another tree
Here are two binary trees, root and subRoot. Verify whether the root contains subtrees with the same structure and node values as the subRoot. If it exists, return true; Otherwise, false is returned.
A subtree of a binary tree tree includes a node of the tree and all descendants of this node. A tree can also be regarded as a subtree of its own.
link
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameStructure(TreeNode * root1, TreeNode * root2)
{
if (!root1 && !root2)
return true;
if (!root1 || !root2)
return false;
return root1->val == root2->val &&
isSameStructure(root1->left, root2->left)&&
isSameStructure(root1->right, root2->right);
}
bool isSubtreeHelper(TreeNode * root, TreeNode * subRoot)
{
if (!root)
return false;
return isSameStructure(root, subRoot) ||
isSubtreeHelper(root->left, subRoot) ||
isSubtreeHelper(root->right, subRoot);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
return isSubtreeHelper(root, subRoot);
}
};
KY11 binary tree traversal
Make a program to read a string of preorder traversal strings entered by the user, and establish a binary tree (stored in pointer mode) according to this string. For example, the following preorder traversal strings: ABC##DE#G##F### where "#" represents a space, and the space character represents an empty tree. After the binary tree is established, the binary tree is traversed in order, and the traversal result is output.
Enter Description:
The input includes 1 line of string, and the length does not exceed 100.
Output Description:
There may be multiple groups of test data. For each group of data, output the sequence traversed in the middle order after the input string is established into a binary tree, and there is a space after each character. Each output result occupies one line.
Example 1
Input:
abc##de#g##f###
copy
Output:
c b e g d f a
link
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>
typedef struct Node
{
char ch;
struct Node * left;
struct Node * right;
}Node;
Node * BuyOneNode()
{
Node * node = (Node *)malloc(sizeof(Node));
if (!node)
{
assert(0);
return NULL;
}
node->left = node->right = NULL;
return node;
}
void InOrderTraver(Node * root)
{
if (!root)
return;
InOrderTraver(root->left);
printf("%c ", root->ch);
InOrderTraver(root->right);
}
Node * CreateBitNode(char str[], int *index,int len, char invalid)
{
if (*index < len && str[*index] != invalid)
{
Node * root = BuyOneNode();
root->ch = str[*index];
*index += 1;
root->left = CreateBitNode(str, index, len, invalid);
*index += 1;
root->right = CreateBitNode(str, index, len, invalid);
return root;
}
return NULL;
}
void DestroyBitNode(Node ** root)
{
if (!(*root))
return;
DestroyBitNode(&(*root)->left);
DestroyBitNode(&(*root)->right);
free(*root);
*root = NULL;
}
int main()
{
char str[100];
while (scanf("%s", str) != EOF)
{
int len = strlen(str);
int index = 0;
Node * root = CreateBitNode(str, &index, len, '#');
InOrderTraver(root);
printf("\n");
DestroyBitNode(&root);
}
return 0;
}