Table of contents
2, DFS traversal OJ actual combat
Lituo 144. Preorder traversal of binary tree
Lituo 94. Inorder traversal of binary tree
Lituo 145. Post-order traversal of binary tree
Leek 105. Construct a Binary Tree from Preorder and Inorder Traversal Sequences
Leek 106. Construct a Binary Tree from Inorder and Postorder Traversal Sequences
Leek 889. Construct a binary tree based on pre-order and post-order traversal
CSU 1283 Binary Tree Traversals
Rico 404. The sum of the left leaves
Likou 1430. Determine whether a given sequence is a path from root to leaf of a binary tree
Leek 1973. Number of nodes whose value is equal to the sum of child node values
Leetcode 1120. Maximum Average of Subtrees
Lituo 1612. Check whether two binary expression trees are equivalent
Lituo 102. Level order traversal of binary tree
Lituo 107. Level order traversal of binary tree II
Leetcode 1161. Maximum layer element sum
Sword Finger Offer 32 - I. Print Binary Tree from Top to Bottom
Sword Finger Offer 32 - III. Print Binary Tree from Top to Bottom III
Lituo 1602. Find the nearest right node in a binary tree
1. DFS traversal
A binary tree cannot be determined by only one traversal, and a binary tree can be determined by inorder + preorder or postorder,
Preorder + postorder may or may not be able to determine a binary tree.
University Data Structure Experiment:
Build a binary tree based on the input data;
Use pre-order, in-order and post-order traversal methods to display the traversal results of the output binary tree
code:
#include<iostream>
using namespace std;
struct node //define node
{
char ch;
struct node *lchild;
struct node *rchild;
};
node * create(struct node *p) //Use the recursive function to create a binary tree in order, with 0 representing empty
{
char c;
cin >> c;
if (c == '0')p = NULL;
else
{
p = new node;
p->ch = c;
p->lchild = create(p->lchild);
p->rchild = create(p->rchild);
}
return p;
}
void preOrder(node *p) //Preorder traversal using recursive functions
{
if (p)
{
cout << p->ch << " ";
preOrder(p->lchild);
preOrder(p->rchild);
}
}
void inOrder(node *p) //Inorder traversal using recursive functions
{
if (p)
{
inOrder(p->lchild);
cout << p->ch << " ";
inOrder(p->rchild);
}
}
void postOrder(node *p) //Using recursive functions, post-order traversal
{
if (p)
{
postOrder(p->lchild);
postOrder(p->rchild);
cout << p->ch << " ";
}
}
int main()
{
node *root = new node;
cout << "Enter the character stored in the binary tree, 0 means it does not exist" << endl;
root = create(root); //Error-prone point 1
cout << "Preorder traversal is ";
preOrder(root);
cout << endl << "Inorder traversal is ";
inOrder(root);
cout << endl << "Postorder traversal is ";
postOrder(root);
system("pause>nul");
return 0;
}Binary tree used for testing:
operation result:
2, DFS traversal OJ actual combat
Lituo 144. Preorder traversal of binary tree
topic:
Given a binary tree, return its preorder traversal.
Example:
Input: [1,null,2,3]
1
\
2
/
3
output: [1,2,3]
Advanced: Recursive algorithm is very simple, can you complete iterative algorithm?
code:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>v1;
if (root == NULL)return v1;
v1.insert(v1.end(), root->val);
vector<int>v2 = preorderTraversal(root->left);
v1.insert(v1.end(), v2.begin(), v2.end());
v2 = preorderTraversal(root->right);
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
};Lituo 94. Inorder traversal of binary tree
topic:
Given a binary tree, return its inorder traversal.
Example:
Input: [1,null,2,3]
1
\
2
/
3
output: [1,3,2]
Advanced: Recursive algorithm is very simple, can you complete iterative algorithm?
code:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>v1;
if (root == NULL)return v1;
v1 = inorderTraversal(root->left);
v1.insert(v1.end(), root->val);
vector<int>v2 = inorderTraversal(root->right);
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
};Lituo 145. Post-order traversal of binary tree
topic:
Given a binary tree, return its postorder traversal.
Example:
Input: [1,null,2,3]
1
\
2
/
3
output: [3,2,1]
Advanced: Recursive algorithm is very simple, can you complete iterative algorithm?
code:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>v1;
if (root == NULL)return v1;
vector<int>v2 = postorderTraversal(root->left);
v1.insert(v1.end(), v2.begin(), v2.end());
v2 = postorderTraversal(root->right);
v1.insert(v1.end(), v2.begin(), v2.end());
v1.insert(v1.end(), root->val);
return v1;
}
};Leek 105. Construct a Binary Tree from Preorder and Inorder Traversal Sequences
Constructs a binary tree based on the preorder and inorder traversal of a tree.
Notice:
You can assume that there are no duplicate elements in the tree.
For example, given
Preorder traversal preorder = [3,9,20,15,7]
Inorder traversal inorder = [9,3,15,20,7]
Returns a binary tree like this:
3
/ \
9 20
/ \
15 7
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder,int s1, vector<int>& inorder, int s2, int len) {
if(len<=0)return NULL;
TreeNode *ans=new TreeNode;
ans->val=preorder[s1];
auto loc=find(inorder.begin()+s2,inorder.begin()+s2+len,preorder[s1]);
ans->left=buildTree(preorder,s1+1,inorder,s2,loc-inorder.begin()-s2);
ans->right=buildTree(preorder,loc-inorder.begin()-s2+s1+1,inorder,loc-inorder.begin()+1,len-(loc-inorder.begin()-s2)-1);
return ans;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder,0,inorder,0,inorder.size());
}
};Leek 106. Construct a Binary Tree from Inorder and Postorder Traversal Sequences
Constructs a binary tree based on the inorder traversal and postorder traversal of a tree.
Notice:
You can assume that there are no duplicate elements in the tree.
For example, given
Inorder traversal inorder = [9,3,15,20,7]
Postorder traversal postorder = [9,15,7,20,3]
Returns a binary tree like this:
3
/ \
9 20
/ \
15 7
class Solution {
public:
TreeNode* buildTree(vector<int>& postorder,int s1, vector<int>& inorder,int s2, int len) {
if(len<=0)return NULL;
TreeNode *ans=new TreeNode;
ans->val=postorder[s1+len-1];
auto loc=find(inorder.begin()+s2,inorder.begin()+s2+len,postorder[s1+len-1]);
ans->left=buildTree(postorder,s1,inorder,s2,loc-inorder.begin()-s2);
ans->right=buildTree(postorder,loc-inorder.begin()-s2+s1,inorder,loc-inorder.begin()+1,len-(loc-inorder.begin()-s2)-1);
return ans;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(postorder,0,inorder,0,inorder.size());
}
};Leek 889. Construct a binary tree based on pre-order and post-order traversal
Returns any binary tree matching the given preorder and postorder traversals.
The values in the pre and post traversals are distinct positive integers.
Example:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
hint:
1 <= pre.length == post.length <= 30
Both pre[] and post[] are permutations of 1, 2, ..., pre.length
Each input is guaranteed to have at least one answer. If there are multiple answers, one of them can be returned.
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder,int s1, vector<int>& inorder, int s2, int len) {
if(len<=0)return NULL;
TreeNode *ans=new TreeNode;
ans->val=preorder[s1];
if(len==1)return ans;
auto loc=find(inorder.begin()+s2,inorder.begin()+s2+len,preorder[s1+1]);
ans->left=buildTree(preorder,s1+1,inorder,s2,loc-inorder.begin()-s2+1);
ans->right=buildTree(preorder,loc-inorder.begin()-s2+s1+2,inorder,loc-inorder.begin()+1,len-(loc-inorder.begin()-s2)-2);
return ans;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder,0,inorder,0,inorder.size());
}
};CSU 1283 Binary Tree Traversals
topic:
Description
Given the preorder sequence obtained by preorder traversal of a binary tree and the postorder sequence obtained by subsequent traversal, can this binary tree be uniquely determined?
Input
The first line of input data contains an integer T (1 <= T <= 100), indicating that there will be a total of T sets of test data next.
For each set of test data, the first line contains a positive integer N (1 <= N <= 26), indicating that the binary tree has a total of N nodes. Each of the next two lines contains N different uppercase letters, and there is no space between the characters, which respectively represent the pre-order sequence and post-order sequence obtained after pre-order traversal and post-order traversal of the binary tree. The data guarantees that at least one binary tree can be constructed according to the preorder sequence and the subsequent sequence.
Output
For each set of test data, if a binary tree can be uniquely determined according to the preorder sequence and the subsequent sequence, output N uppercase letters in one line, and there should be no spaces between characters, indicating the inorder sequence of the binary tree. If a binary tree cannot be uniquely determined, output "-1" in one line (without quotation marks).
Sample Input
2
2
AB
BA
3
ABC
BCA
Sample Output
-1
BAC
code:
#include<iostream>
using namespace std;
char s1[27], s2[27], s3[27];
bool f(int k1, int k2, int k3, int len)
{
if (len == 1)
{
s3[k3] = s1[k1];
return true;
}
char c = s1[k1 + 1];
for (int i = k2; i < k2 + len; i++)
{
if (s2[i] != c)continue;
if (i == k2 + len - 2)return false;
if (!f(k1 + 1, k2, k3, i - k2 + 1))return false;
if (!f(k1 - k2 + i + 2, i + 1, k3 - k2 + i + 2, k2 + len - 2 - i))return false;
s3[k3 - k2 + i + 1] = s1[k1];
}
return true;
}
int main()
{
int t, n;
cin >> t;
while (t--)
{
cin >> n >> s1 >> s2;
s3[n] = '\0';
if (f(0, 0, 0, n))cout << s3 << endl;
else cout << "-1\n";
}
return 0;
}Rico 404. The sum of the left leaves
Given the root node root of a binary tree, return the sum of all left leaves.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: In this binary tree, there are two left leaves, 9 and 15, so return 24
Example 2:
Input: root = [1]
output: 0
hint:
The number of nodes is in the range [1, 1000]
-1000 <= Node.val <= 1000
class Solution {
public:
void sumOfLeftLeaves(TreeNode* root, bool isLeft) {
if (!root->left && !root->right) {
if(isLeft)s += root->val;
return;
}
if (root->left)sumOfLeftLeaves(root->left, true);
if (root->right)sumOfLeftLeaves(root->right, false);
}
int sumOfLeftLeaves(TreeNode* root) {
if (!root)return 0;
s = 0;
sumOfLeftLeaves(root, false);
return s;
}
private:
int s;
};Likou 1430. Determine whether a given sequence is a path from root to leaf of a binary tree
Given a binary tree, we call the sequence of node values in any path from the root node to any leaf node a "valid sequence" of the binary tree. Checks whether a given sequence is a "valid sequence" for the given binary tree.
We give this sequence as an integer array arr. The sequence of node values in any path from the root node to any leaf node is the "valid sequence" of this binary tree.
Example 1:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation:
The path 0 -> 1 -> 0 -> 1 is a "valid sequence" (green nodes in the diagram).
Other "valid sequences" are:
0 -> 1 -> 1 -> 0
0 -> 0 -> 0
Example 2:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
output: false
Explanation: The path 0 -> 0 -> 1 does not exist, so this is not a "sequence".
Example 3:
Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but not a "valid sequence" (Translator's Note: Because the end of the sequence is not a leaf node).
hint:
1 <= arr.length <= 5000
0 <= arr[i] <= 9
The value range of each node is [0 - 9]
class Solution {
public:
bool dfs(TreeNode* root, vector<int>& arr, int loc)
{
if (root->val != arr[loc])return false;
if (!root->left && !root->right && loc == arr.size() - 1)return true;
if ((!root->left && !root->right) || loc == arr.size() - 1)return false;
if(root->left && dfs(root->left, arr, loc + 1))return true;
if(root->right && dfs(root->right, arr, loc + 1))return true;
return false;
}
bool isValidSequence(TreeNode* root, vector<int>& arr) {
if (!root)return false;
return dfs(root, arr, 0);
}
};Leek 1973. Number of nodes whose value is equal to the sum of child node values
Given the root node root of a binary tree, return the number of nodes that meet the condition: the value of the node is equal to the sum of the values of all child nodes of the node.
A child node of a node x refers to the nodes on the path from node x to all leaf nodes. The sum of children of a node with no children is treated as 0 .
Example 1:
Input: root = [10,3,4,2,1] output: 2 Explanation: For a node with a value of 10: the sum of its child nodes is: 3+4+2+1 = 10. For a node with a value of 3: the sum of its child nodes is: 2+1 = 3.
Example 2:
Input: root = [2,3,null,2,null] output: 0 Explanation: There is no node whose value is equal to the sum of its children.
Example 3:
Input: root = [0] output: 1 Explanation: For a node with a value of 0: because it has no child nodes, the sum of its own points is 0.
hint:
- Range of number of nodes in the tree: [1, 105]
- 0 <= Node.val <= 105
class Solution {
public:
int ans = 0;
long long dfs(TreeNode* root)
{
if (!root)return 0;
long long n = dfs(root->left) + dfs(root->right);
if (root->val == n)ans++;
return root->val + n;
}
int equalToDescendants(TreeNode* root) {
dfs(root);
return ans;
}
};Leetcode 1120. Maximum Average of Subtrees
Give you the root node root of a binary tree, find the maximum value of the average value of each subtree of this tree.
A subtree is a collection of any node in the tree and all its descendants.
The mean of a tree is the sum of the node values in the tree divided by the number of nodes.
Example:
Input: [5,6,1]
Output: 6.00000
Explanation:
Taking the node with value = 5 as the root node of the subtree, the average value obtained is (5 + 6 + 1) / 3 = 4.
Taking the node with value = 6 as the root node of the subtree, the average value obtained is 6 / 1 = 6.
Taking the node with value = 1 as the root node of the subtree, the average value obtained is 1 / 1 = 1.
So the answer takes the maximum value of 6.
hint:
The number of nodes in the tree is between 1 and 5000.
Each node has a value between 0 and 100000.
A result is considered correct if it is within 10^-5 of the standard answer.
class Solution {
public:
double ans = -1234567;
void dfs(TreeNode* root, int& s, int& num)
{
if (!root) {
s = 0, num = 0;
return;
}
int s1, num1, s2, num2;
dfs(root->left, s1, num1);
dfs(root->right, s2, num2);
s = s1 + s2 + root->val, num = num1 + num2 + 1;
ans = max(ans, s * 1.0 / num);
}
double maximumAverageSubtree(TreeNode* root) {
int s, num;
dfs(root, s, num);
return ans;
}
};Lituo 1612. Check whether two binary expression trees are equivalent
A binary expression tree is a binary tree that expresses arithmetic expressions. Every node in a binary expression tree has zero or two child nodes. Leaf nodes (nodes with 0 children) represent operands, and non-leaf nodes (nodes with 2 children) represent operators. In this problem, we only consider the '+' operator (i.e. addition).
Given the root nodes root1 and root2 of two binary expression trees. Returns true if the two binary expression trees are equivalent, false otherwise.
When the variables in two binary search trees take any value and the values obtained respectively are equal, we say that the two binary expression trees are equivalent.
Example 1:
Input: root1 = [x], root2 = [x]
output: true
Example 2:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
Output: true
Explanation: a + (b + c) == (b + c) + a
Example 3:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
output: false
Explanation: a + (b + c) != (b + d) + a
hint:
The number of nodes in the two trees is equal, and the number of nodes is an odd number in the range [1, 4999].
Node.val is '+' or a lowercase English letter.
The given tree is guaranteed to be a valid binary expression tree.
Advanced: When your answer needs to support the '-' operator (subtraction) at the same time, how should you modify your answer
template<typename T>
vector<T> vecAdd(const vector<T>& v1, const vector<T>& v2)
{
vector<T>v(max(v1.size(), v2.size()));
for (int i = 0; i < v.size(); i++)v[i] = 0;
for (int i = 0; i < v1.size(); i++)v[i] += v1[i];
for (int i = 0; i < v2.size(); i++)v[i] += v2[i];
return v;
}
class Solution {
public:
vector<int> dfs(Node* r)
{
vector<int> v(26);
if (!r)return v;
if (r->val >= 'a' && r->val <= 'z')v[r->val - 'a'] = 1;
vector<int>v1 = dfs(r->left);
vector<int>v2 = dfs(r->right);
v = vecAdd(v, v1);
v = vecAdd(v, v2);
return v;
}
bool checkEquivalence(Node* r1, Node* r2) {
vector<int> v1 = dfs(r1);
vector<int> v2 = dfs(r2);
for (int i = 0; i < 26; i++)if (v1[i] != v2[i])return false;
return true;
}
};3. BFS traversal
Lituo 102. Level order traversal of binary tree
Given a binary tree, please return the node values obtained by layer order traversal. (ie layer by layer, visit all nodes from left to right).
Example:
Binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Return its level order traversal result:
[
[3],
[9,20],
[15,7]
]
class Solution {
public:
void levelOrder(vector<vector<TreeNode*>>&v){
vector<TreeNode*>v1=*(v.end()-1);
vector<TreeNode*>v2;
for(int i=0;i<v1.size();i++){
if(v1[i]->left)v2.push_back(v1[i]->left);
if(v1[i]->right)v2.push_back(v1[i]->right);
}
if(v2.empty())return;
v.push_back(v2);
levelOrder(v);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<vector<int>>ans;
vector<int>tmpans;
if(!root)return ans;
tmp.push_back(root);
v.push_back(tmp);
levelOrder(v);
for(int i=0;i<v.size();i++){
tmpans.resize(v[i].size());
for(int j=0;j<v[i].size();j++)tmpans[j]=v[i][j]->val;
ans.push_back(tmpans);
}
return ans;
}
};Lituo 107. Level order traversal of binary tree II
Given a binary tree, return a bottom-up level-order traversal of its node values. (That is, traverse from left to right layer by layer from the layer where the leaf node is located to the layer where the root node is located)
For example:
Given a binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Return its bottom-up level-order traversal as:
[
[15,7],
[9,20],
[3]
]
It is the same as Lituo 102. The level order traversal of the binary tree is the same, only need to flip it.
class Solution {
public:
void levelOrder(vector<vector<TreeNode*>>&v){
vector<TreeNode*>v1=*(v.end()-1);
vector<TreeNode*>v2;
for(int i=0;i<v1.size();i++){
if(v1[i]->left)v2.push_back(v1[i]->left);
if(v1[i]->right)v2.push_back(v1[i]->right);
}
if(v2.empty())return;
v.push_back(v2);
levelOrder(v);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<vector<int>>ans;
vector<int>tmpans;
if(!root)return ans;
tmp.push_back(root);
v.push_back(tmp);
levelOrder(v);
for(int i=v.size()-1;i>=0;i--){
tmpans.resize(v[i].size());
for(int j=0;j<v[i].size();j++)tmpans[j]=v[i][j]->val;
ans.push_back(tmpans);
}
return ans;
}
};Leetcode 1161. Maximum layer element sum
You are given the root node root of a binary tree. Let the root node be at level 1 of the binary tree, and the child nodes of the root node be at level 2, and so on.
Please return the layer numbers of the layers (there may be only one layer) with the largest sum of elements in the layer, and return the smallest among them.
Example 1:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
The sum of the elements of the first layer is 1,
The sum of the elements of the second layer is 7 + 0 = 7,
The sum of the elements of the third layer is 7 + -8 = -1,
So we return the layer number of layer 2, which has the largest sum of elements in the layer.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
hint:
The number of nodes in the tree is in the range [1, 104]
-105 <= Node.val <= 105
class Solution {
public:
void levelOrder(vector<vector<TreeNode*>>&v) {
vector<TreeNode*>v1 = *(v.end() - 1);
vector<TreeNode*>v2;
for (int i = 0; i < v1.size(); i++) {
if (v1[i]->left)v2.push_back(v1[i]->left);
if (v1[i]->right)v2.push_back(v1[i]->right);
}
if (v2.empty())return;
v.push_back(v2);
levelOrder(v);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<vector<int>>ans;
vector<int>tmpans;
if (!root)return ans;
tmp.push_back(root);
v.push_back(tmp);
levelOrder(v);
for (int i = 0; i < v.size(); i++) {
tmpans.resize(v[i].size());
for (int j = 0; j < v[i].size(); j++)tmpans[j] = v[i][j]->val;
ans.push_back(tmpans);
}
return ans;
}
int maxLevelSum(TreeNode* root) {
vector<vector<int>>v = levelOrder(root);
int m = INT_MIN;
int ans = 0;
for (int i = 0; i < v.size(); i++) {
int s = 0;
for (auto vi : v[i])s += vi;
if (m < s)m = s, ans = i + 1;
}
return ans;
}
};Sword Finger Offer 32 - I. Print Binary Tree from Top to Bottom
Print each node of the binary tree from top to bottom, and the nodes at the same level are printed from left to right.
For example:
Given a binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return:
[3,9,20,15,7]
hint:
Total number of nodes <= 1000
Idea: Just use the above answer to transform it, and it will be done in one line.
//2 vector s are stitched together
template<typename T>
vector<T> join(const vector<T>& v1, const vector<T>& v2)
{
vector<T>ans(v1.size() + v2.size());
copy(v1.begin(), v1.end(), ans.begin());
copy(v2.begin(), v2.end(), ans.begin() + v1.size());
return ans;
}
template<typename T>
vector<T> join(const vector<vector<T>> &v)
{
vector<T>ans;
for (auto &vi : v)ans = join(ans, vi);
return ans;
}
class Solution {
public:
void levelOrder3(vector<vector<TreeNode*>>&v) {
vector<TreeNode*>v1 = *(v.end() - 1);
vector<TreeNode*>v2;
for (int i = 0; i < v1.size(); i++) {
if (v1[i]->left)v2.push_back(v1[i]->left);
if (v1[i]->right)v2.push_back(v1[i]->right);
}
if (v2.empty())return;
v.push_back(v2);
levelOrder3(v);
}
vector<vector<int>> levelOrder2(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<vector<int>>ans;
vector<int>tmpans;
if (!root)return ans;
tmp.push_back(root);
v.push_back(tmp);
levelOrder3(v);
for (int i = 0; i < v.size(); i++) {
tmpans.resize(v[i].size());
for (int j = 0; j < v[i].size(); j++)tmpans[j] = v[i][j]->val;
ans.push_back(tmpans);
}
return ans;
}
vector<int> levelOrder(TreeNode* root) {
return join(levelOrder2(root));
}
};Sword Finger Offer 32 - III. Print Binary Tree from Top to Bottom III
Please implement a function to print the binary tree in zigzag order, that is, the first line is printed from left to right, the second layer is printed from right to left, the third line is printed from left to right, and the others and so on.
For example:
Given a binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Return its level traversal result:
[
[3],
[20,9],
[15,7]
]
hint:
Total number of nodes <= 1000
Based on the answer of Jianzhi Offer 32 - II. Print binary tree from top to bottom II, add a flip.
//flip vector
template<typename T>
vector<T> frev(const vector<T>& v)
{
vector<T> ans;
ans.resize(v.size());
for (int i = 0; i < v.size(); i++)ans[i] = v[v.size() - 1 - i];
return ans;
}
class Solution {
public:
void levelOrder(vector<vector<TreeNode*>>&v){
vector<TreeNode*>v1=*(v.end()-1);
vector<TreeNode*>v2;
for(int i=0;i<v1.size();i++){
if(v1[i]->left)v2.push_back(v1[i]->left);
if(v1[i]->right)v2.push_back(v1[i]->right);
}
if(v2.empty())return;
v.push_back(v2);
levelOrder(v);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<vector<int>>ans;
vector<int>tmpans;
if(!root)return ans;
tmp.push_back(root);
v.push_back(tmp);
levelOrder(v);
for(int i=0;i<v.size();i++){
tmpans.resize(v[i].size());
for(int j=0;j<v[i].size();j++)tmpans[j]=v[i][j]->val;
ans.push_back(tmpans);
}
for(int i=1;i<ans.size();i+=2)ans[i]=frev(ans[i]);
return ans;
}
};Lituo 1602. Find the nearest right node in a binary tree
Given the root node root of a binary tree and a node u in the tree, return the nearest right node in the layer where u is, or null when u is the rightmost node in the layer.
Example 1:
Input: root = [1,2,3,null,4,5,6], u = 4
Output: 5
Explanation: In the layer where node 4 is located, the nearest right node is node 5.
Example 2:
Input: root = [3,null,4,2], u = 2
Output: null
Explanation: There are no nodes on the right side of 2.
Example 3:
Input: root = [1], u = 1
Output: null
Example 4:
Input: root = [3,4,2,null,null,null,1], u = 4
Output: 2
hint:
The range of the number of nodes in the tree is [1, 105] .
1 <= Node.val <= 105
The values of all nodes in the tree are unique.
u is a node of a binary tree rooted at root.
class Solution {
public:
TreeNode* tar;
int tarDeep;
void levelOrder(vector<vector<TreeNode*>>&v, int deep){
vector<TreeNode*>v1=*(v.end()-1);
vector<TreeNode*>v2;
for(int i=0;i<v1.size();i++){
if(v1[i]==tar)tarDeep=deep;
if(v1[i]->left)v2.push_back(v1[i]->left);
if(v1[i]->right)v2.push_back(v1[i]->right);
}
if(v2.empty())return;
v.push_back(v2);
levelOrder(v, deep+1);
}
vector<vector<TreeNode*>> levelOrder(TreeNode* root) {
vector<vector<TreeNode*>>v;
vector<TreeNode*>tmp;
vector<int>tmpans;
if(!root)return v;
tmp.push_back(root);
v.push_back(tmp);
levelOrder(v, 0);
return v;
}
TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
tar = u;
auto v = levelOrder(root);
cout<<tarDeep;
cout<<v.size();
for(int i=0;i<v[tarDeep].size();i++){
if(v[tarDeep][i]!=u)continue;
if(i==v[tarDeep].size()-1)return NULL;
return v[tarDeep][i+1];
}
return NULL;
}
};