【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

Leecode 112. Sum of paths

You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

Input: root = [13,4,7,2 5,4,8,11, null, null, null, null, 1], targetSum = 22

Output: true,

Enter: root = [1,2,3], targetSum = 5

Output: false

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

Let’s take this tree as an example

Find a tree recursively from the top down, subtract the left subtree and the right subtree from the target value sum, and see if it equals nothing.

Because equal to null means that the left or right node of the tree is the last child node.

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return sum == root.Val
    }
    return hasPathSum(root.Left, sum - root.Val) || hasPathSum(root.Right, sum - root.Val)
}


Copy the code

The iterative version

The iterative version is also very simple, using stacks or queues

Is it better to think about queue or stack? If the left or right node is not empty, we join the queue. If the left or right node is not empty, we continue to queue. If the sum of the sums equals the target value, the result is true.

  1. Define a queue node and save the tree (FIFO)

  2. Define a queue val to record the cumulative value

  3. Initialize the queue node and add the whole tree to the queue, because I also need to judge by the left or right node of the tree.

  4. Take out the root node and record the accumulated value as the root node

  5. Queue node element, not 0, because we need to determine whether the tree has been traversed

  6. Fetch an element from the queue node, which is the tree to which it was added

  7. From queue val, fetch the root node, which is the cumulative value

8. If the left or right node is empty, it indicates the end, check whether the sum equals the target value, if so return true.

  1. The left node of the extracted tree is not empty. Add the tree with the left node as the root to queue node. The sum of queue val = sum + the root of the left subtree with the left node as the root, which is itself. Go back to step 5 and go down.

  2. The right node of the extracted tree is not empty. Add the tree with the right root to queue node. The sum of queue val = sum + the root of the right subtree with the right root, which is itself. Go back to step 5 and go down.

11. If the tree is traversed and no target value is found, return false.

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    queNode := []*TreeNode{}    / / 1.
    queVal := []int{}           / / 2.
    queNode = append(queNode, root)  / / 3.
    queVal = append(queVal, root.Val)  / / 4.
    for len(queNode) != 0 {         / / 5.
        now := queNode[0]           / / 6.
        queNode = queNode[1:]
        temp := queVal[0]           / / 7.
        queVal = queVal[1:]
        if now.Left == nil && now.Right == nil {   / / 8.
            if temp == sum {
                return true
            }
            continue
        }
        ifnow.Left ! = nil {/ / 9.
            queNode = append(queNode, now.Left)
            queVal = append(queVal, now.Left.Val + temp)
        }
        ifnow.Right ! = nil {/ / 10.
            queNode = append(queNode, now.Right)
            queVal = append(queVal, now.Right.Val + temp)
        }
    }
    return false
}



Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️