D15 (Binary tree 02 level-order traversal, pre- and post-order recursion) level-order traversal*10 226. Flip binary tree 101. Symmetric binary tree

Table of Contents

Layer sequential traversal*10

102. Level-order traversal of binary tree

Sequence iteration

preorder recursion

107. Level-order traversal of binary trees II

199. Right view of binary tree

637. Level average of binary tree

429. Level-order traversal of N-ary tree

515. Find the maximum value in each tree row

116. Populate the next right node pointer of each node

117. Fill the next right node pointer of each node II

104. Maximum depth of binary tree

111. Minimum depth of binary tree

226. Flip a binary tree

Preorder recursion:

Thought process:

Likou code:

101. Symmetric binary tree

Postorder recursion:

Thought process:

Solution details

Likou code:

END

Level-order traversal can be modified on the same set of code.

Level-order traversal*10

102. Level-order traversal of a binary tree

Level Sequence Iteration

/**
 * 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) {}
 * };
 */

// (iterative method) queue: first in, first out
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*>que;
        if (root != nullptr) que.push(root);

        while (!que.empty()) {
            vector<int>vec;
            int size = que.size();

            for (int i = 0; i < size; i + + ) { // Traverse the nodes of each layer
                TreeNode* p = que.front();
                que.pop();
                vec.push_back(p->val);

                if (p->left) que.push(p->left);
                if (p->right) que.push(p->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

Preorder recursion

/**
 * 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) {}
 * };
 */

// recursive method
//Input parameters: current node pointer TreeNode* cur, two-dimensional array to store the result vector<vector<int>> depth & amp; vec, binary tree sequence
// Return value: void return value
//Single-layer logic: Return when the pointer is empty; determine the current level, and if the current layer is traversed, expand the next layer; the root node continuously expands the left and right child nodes;
// Termination condition: pointer is null;

class Solution {
private:
    void order(TreeNode* cur, vector<vector<int>> & amp; vec, int depth) { // Here depth is passed as a numerical value. Modifications within the function do not affect the values outside the function.
        if (cur == nullptr) return;
        if (vec.size() == depth) vec.push_back(vector<int>()); // Write an empty one-dimensional array and expand it by one layer

        vec[depth].push_back(cur->val);
        order(cur->left, vec, depth + 1);
        order(cur->right, vec, depth + 1);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};c

107. Level-order traversal of binary trees II

Give you the root node root of the binary tree and return its node value Bottom-up level order traversal. (That is, traverse from left to right layer by layer from the layer where the leaf node is to the layer where the root node is)

reverse(result.begin(), result.end()); // Add a line of reversal on the top-down basis

199. Right view of binary tree

Given the root node root of a binary tree, imagine yourself standing on the right side of it, and return the nodes that can be seen from the right in order from top to bottom. value.

if (i == size-1) result.push_back(p->val);

637. Level average of binary tree

Given the root node of a non-empty binary tree
root , returns the average value of nodes in each layer in the form of an array. differ from the actual answer
Answers within 10-5 are accepted.

{
    sum + = p->val;
}
result.push_back(sum/size);

429. Level-order traversal of N-ary tree

for (int i = 0; i < p->children.size(); i + + ) {
    if (p->children[i] != nullptr)
        que.push(p->children[i]);
}

515. Find the maximum value in each tree row

Given the root node of a binary tree
root , please find the maximum value of each level in the binary tree.

int max_num = INT_MIN; // INT_MIN Minimum value of int type -2147483648

{
    if (p->val > max_num) max_num = p->val; // Record the maximum value of each layer
}

116. Fill the next right node pointer of each node

Given a Perfect Binary Tree, all its leaf nodes are at the same level and each parent node has two child nodes.

if (i == size-1) p->next = nullptr;
else p->next = que.front();

117. Fill the next right node pointer II of each node

Given an arbitrary binary tree (the code remains the same compared to the previous question)

if (i == size-1) p->next = nullptr;
else p->next = que.front();

104. The maximum depth of a binary tree

Given a binary tree root , return its maximum depth.

The maximum depth of a binary tree is the number of nodes on the longest path from the root node to the farthest leaf node.

result + + ; // For each level of traversal, + +

111. The minimum depth of a binary tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

Explanation: Leaf nodes refer to nodes that have no child nodes.

Search layer by layer, when a leaf node (not a root node) is encountered, it is the minimum depth.

result + + ;
{
    if (p != root & amp; & amp; p->left == nullptr & amp; & amp; p->right == nullptr) return result;
}

226. Flip Binary Tree

Question link: 226. Flip a binary tree

Given the root node root of a binary tree, flip the binary tree and return its root node.

Example 1:
Input:root = [4,2,7,1,3,6,9]
Output:[4,7,2,9,6,3,1]
Example 2:
Input:root = [2,1,3]
Output:[2,3,1]
Example 3:
Input:root = []
Output:[]

Preorder recursion:

Thinking process:

To flip a binary tree, you only need to flip the left and right of each node.

But the key is, which traversal method is used?

Depth first (recursive method, iterative method in front, middle and last order), breadth first (level order traversal, iterative method)

Prioritize mastering the recursive method:

Input and return: TreeNode* invertTree(TreeNode* root);

Single-layer logic: exchange left and right nodes;

Termination condition: The node pointer is empty;

Liqun code:

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root; // medium
        swap(root->left, root->right);
        invertTree(root->left); // left
        invertTree(root->right); // right
        return root;
    }
};

101. Symmetric Binary Tree

Question link: 101. Symmetric binary tree

Give you the root node root of a binary tree and check whether it is axially symmetrical.

Example 1:
Input:root = [1,2,2,3,4,4,3]
Output:true
Example 2:
Input:root = [1,2,2,null,3,null,3]
Output:false

Postorder recursion:

Thinking process:

Compare whether the inner and outer elements of two subtrees are equal;

Need to think about which traversal method to use? Pre-middle and post-order recursive traversal–>Adopt post-order traversal

Recursive three-step thinking:

Input and return values: TreeNode* left, TreeNode* right left subtree node right subtree node

Termination condition: Determine whether the pointers of the two nodes are empty nodes and whether the values are equal, otherwise false will be returned directly;

Single-layer recursive logic: handle the situation where the left and right nodes are both empty and have the same value: determine whether the inner nodes and outer nodes of the two subtrees are equal.

Problem solution details

First, judge whether the pointers of the two nodes are empty nodes and whether the values are equal, otherwise false will be returned directly;

Make sure that both the left and right nodes are empty and have the same value before entering recursion.

Like code:

/**
 * 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 compare(TreeNode* left, TreeNode* right) { // Pointers to the left and right subtrees
        //First exclude empty nodes
        if (left == nullptr & amp; & amp; right != nullptr) return false;
        else if (left != nullptr & amp; & amp; right == nullptr) return false;
        else if (left == nullptr & amp; & amp; right == nullptr) return true;
        // Exclude empty nodes, and then exclude cases where the values are different
        else if (left->val != right->val) return false;

        //The remaining situation is: the left and right nodes are both empty and have the same value
        // Carry out recursion and make the next level of judgment
        bool outside = compare(left->left, right->right); // Left subtree: left Right subtree: right
        bool inside = compare(left->right, right->left); // Left subtree: right Right subtree: left
        bool isSame = outside & amp; & amp; inside; // Left subtree: middle Right subtree: middle
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

END

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 53720 people are learning the system

Level-order traversal*10

102. Level-order traversal of a binary tree

Level Sequence Iteration

Preorder recursion

107. Level-order traversal of binary trees II

199. Right view of binary tree

637. Level average of binary tree

429. Level-order traversal of N-ary tree

515. Find the maximum value in each tree row

116. Fill the next right node pointer of each node

117. Fill the next right node pointer II of each node

104. The maximum depth of a binary tree

111. The minimum depth of a binary tree

226. Flip Binary Tree

Preorder recursion:

Thinking process:

Liqun code:

101. Symmetric Binary Tree

Postorder recursion:

Thinking process:

Problem solution details

Like code:

END