“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

863. All nodes with distance K in a binary tree

Given a binary tree (with root), a target (target), and an integer value k.

Returns a list of values for all nodes whose target distance is k. The answers can be returned in any order

Example 1: 

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], target = 5, k = 2 output:,4,1 [7] : for nodes with target distance (5) for the value of 2 nodes, value respectively, 4, 7 and 1Copy the code

Example 2:

Input: root = [1], target = 1, k = 3Copy the code

Tip:

  • The number of nodes is within the range [1, 500]
  • 0 <= Node.val <= 500
  • All values in node. val are different
  • The target node target is the node in the tree.
  • 0 <= k <= 1000

Recurse up and down from the target node

We are given a binary tree and we specify a target node

If target is 5 in example 1, it does not mean that target is the number 5, but that target is the object with the value 5.

We then give a range k, and collect all the values that are traget k distance, which we can think of as the line connecting two nodes. The distance between the two nodes is 1, so it is the value of the node corresponding to the number k line

Here we start at the target node target and look up and down

Concrete implementation:

  • First, depth-first traverses the entire binary tree, processing all nodes simultaneously, giving them a prev pointing to their parent node
  • Declare two lookup functions after processing
    • Search down each time to determine whether the current distance n is equal to k, is equal to the end of the recursion, otherwise recursively search left and right child nodes, at the same time n+1
    • So if you look up, you start at prev, and when you find the target node, you recurse to the parent node, and then to another child of the parent node, n+1
    • If n===k, store the current node root in res

Finally, return res

var distanceK = function (root, target, k) {
    var stack = [root]
    var res = []
    while (stack.length) {
        var item = stack.pop()
        // Handle left and right
        var left = item.left
        var right = item.right
        if (left) {
            left.prev = item
            stack.push(left)
        }
        if (right) {
            right.prev = item
            stack.push(right)
        }
    }
    // Look down
    function findDown(root, n) {
        if(! root)return
        if (n === k) {
            res.push(root.val)
            return
        }
        findDown(root.left, n + 1)
        findDown(root.right, n + 1)}// Look up
    function findUp(root, n, prev) {
        if(! root)return
        if (n === k) {
            res.push(root.val)
            return
        }
        if (n > k) return
        / / down
        if (root.left && root.left.val === prev) {
            findDown(root.right, n + 1)}if (root.right && root.right.val === prev) {
            findDown(root.left, n + 1)}/ / up
        findUp(root.prev, n + 1, root.val)

    }
    // Process the starting point
    if (k === 0) {
        return [target.val]
    } else {
        // Look down
        findDown(target.left, 1)
        findDown(target.right, 1)
        // Look up
        findUp(target.prev, 1, target.val)
    }
    return res
};
Copy the code