This is the 7th day of my participation in the August Text Challenge.More challenges in August

Antecedent traversal of binary trees

144. Antecedent traversal of binary trees(power button)

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Example 1:

  • Enter: root = [1,null,2,3]
  • Output: [1, 2, 3]

Example 2:

  • Enter: root = []
  • Output: []

Example 3:

  • Enter: root = [1]
  • Output: [1]

Example 4:

  • Enter: root = [1,2]
  • Output: [1, 2]

Example 5:

  • Enter: root = [1,null,2]
  • Output: [1, 2]

Tip:

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Set an ANS as the final return array. Set a recursive method DFS to achieve the whole binary tree before traversal, the specific operation is as follows:

  • Determines whether the node passed in is NULL and terminates execution if it is.
  • Since it is a front-order traversal, the root node is executed first, followed by the left and right nodes. The operation of the root node is to put the root node into an ANS array. The left and right nodes are treated as root nodes respectively, and the recursive operation is performed.
  • Finally, we return to ANS.

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * The recursive algorithm implements the preorder traversal *@param {TreeNode} root
 * @param {number[]} ans* /
var dfs = function(root, ans) {
    if(root == null) return root;
    ans.push(root.val);
    dfs(root.left, ans);
    dfs(root.right, ans);
}
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
    let ans = [];
    dfs(root, ans);
    return ans;
};
Copy the code

Two, N – tree before traversal

589. Antecedent traversal of N fork trees(power button)

Given an n-tree, returns a sequential traversal of its node values.

The n-fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

Progression: recursion is easy, can you use iterative method to complete this problem?

Example 1:

  • Input: root = [1,null,3,2,4,null,5,6]
  • Output:,3,5,6,2,4 [1]

Example 2:

  • Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14]
  • Output:,2,3,6,7,11,14,4,8,12,5,9,13,10 [1]

Tip:

  • The height of an n-tree is less than or equal to 1000
  • The total number of nodes is in the range [0, 10^4]

Source: LeetCode link: leetcode-cn.com/problems/n-… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

N-tree is similar to the pre-order traversal of binary tree, except that binary tree sets left and right nodes, while n-tree puts all child nodes into the children array, and traverses the nodes in the children array to perform recursive operations on the child nodes.

Set an ANS as the final return array. Set a recursive method DFS to achieve the whole n-fork tree before traversal, the specific operation is as follows:

  • Determines whether the node passed in is NULL and terminates execution if it is.
  • Because it is a front-order traversal, the root node is executed first, followed by the child nodes. The operation of the root node is to put the root node into an ANS array. Iterate over all children under the root node, performing recursive operations on them.
  • Finally, we return to ANS.

Code implementation:

/** * // Definition for a Node. * function Node(val, children) { * this.val = val; * this.children = children; *}; * /
/** * The recursive algorithm implements the preorder traversal *@param {TreeNode} root
 * @param {number[]} ans* /
var dfs = function(root, ans){
    if(root == null) return root;
    ans.push(root.val);
    // Iterate over all child nodes recursively
    for(let i = 0; i < root.children.length; i++) { dfs(root.children[i],ans); }}/ * * *@param {Node|null} root
 * @return {number[]}* /
var preorder = function(root) {
    let ans = [];
    dfs(root, ans);
    return ans;
};
Copy the code

Flip the binary tree

226. Flip the binary tree

Flip a binary tree.

Example:

Input:

     4
   /   \
  2     7/ \ \1   3 6   9
Copy the code

Output:

     4
   /   \
  7     2/ \ \9   6 3   1
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

A binary tree can be flipped recursively by switching the positions of all the left and right nodes.

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */

/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
var invertTree = function(root) {
    if(root == null) return root;
    // Switch the left and right nodes
    const temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);
    return root;
};
Copy the code

Print binary tree II from top to bottom

Finger Offer 32-ii. Print binary tree II from top to bottom

The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row.

For example, given a binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3],
  [9.20],
  [15.7]]Copy the code

Warning: The total number of nodes <= 1000

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

If you want to output the node values of each layer, you can choose either of the following ways to traverse the entire binary tree. If you want to traverse the current layer, you can put the current node values into the array of the current layer.

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {number[][]} ans
 * @param {number} deep* /
var dfs = function(root, ans, deep) {
    if(root == null) return;
    // When there is no data in the deep layer, ans adds an empty array to prevent errors when using ans[deep]
    if(deep == ans.length) {
        ans.push([]);
    }
    ans[deep].push(root.val);
    dfs(root.left, ans, deep + 1);
    dfs(root.right, ans, deep + 1);
} 
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {
    let ans = new Array(a); dfs(root, ans,0)
    return ans;
};
Copy the code