This article will show you how to solve N leetCode-related algorithm problems using a tree traversal method.

I am not afraid of the man who has practiced ten thousand kicks, but I am afraid of the man who has practiced one kick ten thousand times.

Tree Traversal

As shown in the figure below, three traversal methods can be realized by the same recursive idea

Sequential traversal (PreOrder, in order of accessing the root node first)

var preorderTraversal = function(root) {
  const res = []
  function traversal (root) {
    if(root ! = =null) {
      res.push(root.val) // Access the root node value
      traversal(root.left) // Recursively traverse the left subtree
      traversal(root.right) // Recursively traverse the right subtree
    }
  }
  traversal(root)
  return res
}
Copy the code

Order traversal in 94 (InOrder, in the order in which the root node is accessed in the middle)

var inorderTraversal = function(root) {
  const res = []
  function traversal (root) {
    if(root ! = =null) {
      traversal(root.left)
      res.push(root.val)
      traversal(root.right)
    }
  }
  traversal(root)
  return res
}
Copy the code

145 Follow-up traversal (PosterOrder, in the order in which the root node is accessed later)

var postorderTraversal = function(root) {
  const res = []
  function traversal (root) {
    if(root ! = =null) {
      traversal(root.left)
      traversal(root.right)
      res.push(root.val)
    }
  }
  traversal(root)
  return res
}
Copy the code

100 Same tree

You can use this recursive idea to climb two trees simultaneously

var isSameTree = function(p, q) {
  function traversal (root1, root2) {
    if (root1 === null&& root2 ! = =null) {
      return false
    } else if(root1 ! = =null && root2 === null) {
      return false
    } else if (root1 === null && root2 === null) {
      return true
    } else {
      return  root1.val === root2.val && traversal(root1.left, root2.left) && traversal(root1.right, root2.right)
    }
  }
  return traversal(p, q)
}
Copy the code

226 Reverse the binary tree

This algorithm could help Homebrew author Max Howell solve Google’s algorithmic interview questions

var invertTree = function(root) {
  function traversal (root) {
    if (root === null) {
      return null
    } else {
      [root.left, root.right] = [traversal(root.right), traversal(root.left)]
      return root
    }
  }
  return  traversal(root)
}
Copy the code

Post-order traversal of a 590 N fork tree

We can also use this algorithm to solve the n-fork tree problem

var postorder = function(root) {
  const res = []
  function traversal (root) {
    if(root ! = =null) {
      root.children.forEach(child= > {
        traversal(child)
      })
      res.push(root.val)
    }
  }
  traversal(root)
  return res
}
Copy the code

If you get tired of writing this, you can write it differently and use anonymous functions

var postorder = function(root) {
  constres = [] ; (function (root) {
    if(root ! = =null) {
      root.children.forEach(child= > {
        arguments.callee(child)
      })
      res.push(root.val)
    }
  })(root)
  return res
}
Copy the code

You can also iterate using stacks

var postorder = function(root) {
  if (root === null) {
    return[]}const res = []
  const arr = [root]
  while (arr.length) {
    const cur = arr.pop()
    res.push(cur.val)
    for (let i = cur.children.length - 1; i >= 0; i--) {
      arr.push(cur.children[i])
    }
  }
  return res.reverse()
}
Copy the code

Serrated level traversal of 103 binary trees

In plain English, snakeskin climbs trees

var zigzagLevelOrder = function(root) {
  if (root === null) {
    return[]}else {
    let res = []
    function traversal (root, depth) {
      if(root ! = =null) {
        if (res[depth] === undefined) {
          res[depth] = []
        }
        res[depth].push(root.val)
        traversal(root.left, depth + 1)
        traversal(root.right, depth + 1)
      }
    }
    traversal(root, 0)
    res.forEach((item, index) = > {
      if (index & 1) {
        res[index] = item.reverse()
      }
    })
    return res
  }
}
Copy the code

To optimize the

var zigzagLevelOrder = function(root) {
  if (root === null) {
    return[]}else {
    let res = []
    function traversal (root, depth) {
      if(root ! = =null) {
        if (res[depth] === undefined) {
          res[depth] = []
        }
        if (depth & 1) {
          res[depth].unshift(root.val)
        } else {
          res[depth].push(root.val)
        }
        traversal(root.left, depth + 1)
        traversal(root.right, depth + 1)
      }
    }
    traversal(root, 0)
    return res
  }
}
Copy the code

230 The KTH smallest element in the binary search tree

var kthSmallest = function (root, k) {
  let arr = []
  function traversal (node) {
    if(node ! = =null) {
      traversal(node.left)
      arr.push(node.val)
      traversal(node.right)
    }
  }
  traversal(root)
  return arr[k - 1]}Copy the code

Optimization, reduce the number of iterations

var kthSmallest = function (root, k) {
  let arr = []
  function traversal(node) {
    if(node ! = =null && arr.length < k) {
      traversal(node.left)
      arr.push(node.val)
      traversal(node.right)
    }
  }
  traversal(root)
  return arr[k - 1]}Copy the code

Optimized further, using O(1) for extra space

var kthSmallest = function (root, k) {
  let res
  let count = 0
  function traversal(node) {
    if(node ! = =null) {
      if (count < k) {
        traversal(node.left)
      }
      if (++count === k) {
        res = node.val
      }
      if (count < k) {
        traversal(node.right)
      }
    }
  }
  traversal(root)
  return res
}
Copy the code

102 Sequence traversal of binary trees

var levelOrder = function(root) {
  const res = []
  function traversal (root, depth) {
    if(root ! = =null) {
      if(! res[depth]) { res[depth] = [] } traversal(root.left, depth +1)
      res[depth].push(root.val)
      traversal(root.right, depth + 1)
    }
  }
  traversal(root, 0)
  return res
}
Copy the code

199 Right view of the binary tree

Basic idea: The value of nodes at each layer depth is recorded in sequence traversal first. The left node is recorded first and then the right node is recorded. Then the value recorded in the end is the value seen in the right view of the layer depth

var rightSideView = function(root) {
  const arr = []
  function traversal (root, depth) {
    if (root) {
      if (arr[depth] === undefined) {
        arr[depth] = []
      }
      arr[depth].push(root.val)
      traversal(root.left, depth + 1)
      traversal(root.right, depth + 1)
    }
  }
  traversal(root, 0)
  const res = []
  for (let i = 0; i < arr.length; ++i) {
    res.push(arr[i][arr[i].length - 1])}return res
};
Copy the code

104 Maximum depth of a binary tree

var maxDepth = function (root) {
  let res = 0
  function traversal (root, depth) {
    if(root ! = =null) {
      if (depth > res) {
        res = depth
      }
      if (root.left) {
        traversal(root.left, depth + 1)}if (root.right) {
        traversal(root.right, depth + 1)
      }
    }
  }
  traversal(root, 1)
  return res
}
Copy the code

107 Hierarchical traversal of binary trees II

var levelOrderBottom = function(root) {
  if (root === null) {
    return[]}let res = []
  function traversal (root, depth) {
    if(root ! = =null) {
      if(! res[depth]) { res[depth] = [] } traversal(root.left, depth +1)
      res[depth].push(root.val)
      traversal(root.right, depth + 1)
    }
  }
  traversal(root, 0)
  return res.reverse()
}
Copy the code

671 The second smallest node in a binary tree

var findSecondMinimumValue = function(root) {
  letarr = [] ; (function traversal (root) {
    if(root ! = =null) {
      traversal(root.left)
      arr.push(root.val)
      traversal(root.right)
    }
  })(root)
  let _arr = [...new Set(arr)].sort()
  return _arr[1]? _arr[1] : -1
}
Copy the code

1038 From binary search tree to larger sum tree

var bstToGst = function(root) {
  let sum = 0
  function traversal (root) {
    if(root ! = =null) {
      traversal(root.right)
      root.val += sum
      sum = root.val
      traversal(root.left)
    }
  }
  traversal(root)
  return root
}
Copy the code

538 Converts binary search tree to summation tree

var convertBST = function(root) {
  let sum = 0
  function traversal (root) {
    if(root ! = =null) {
      traversal(root.right)
      sum += root.val
      root.val = sum
      traversal(root.left)
    }
  }
  traversal(root)
  return root
}
Copy the code

700 binary search tree search

var searchBST = function(root, val) {
  function traversal (root) {
    if(root ! = =null) {
      if (root.val === val) {
        return root
      } else if (root.val < val) {
        return traversal(root.right)
      } else {
        return traversal(root.left)
      }
    } else {
      return root
    }
  }
  return traversal(root)
}
Copy the code

559 Maximum depth of an n-fork tree

var maxDepth = function(root) {
  if (root === null) {
    return 0
  } else {
    let depth = 1
    function traversal (root, curDepth) {
      if(root ! = =null) {
        if (curDepth > depth) {
          depth = curDepth
        }
        root.children.forEach(child= > traversal(child, curDepth + 1))
      }
    }
    traversal(root, 1)
    return depth
  }
}
Copy the code

589 antecedent traversal of n-tree

var preorder = function(root) {
  const res = []
  function traversal (root) {
    if(root ! = =null) {
      res.push(root.val)
      root.children.forEach(child= > traversal(child))
    }
  }
  traversal(root)
  return res
}
Copy the code

897 increasing order search tree

var increasingBST = function(root) {
  const arr = []
  function traversal (root) {
    if(root ! = =null) {
      traversal(root.left)
      arr.push(root.val)
      traversal(root.right)
    }
  }
  traversal(root)
  const res = new TreeNode(arr[0])
  let currentNode = res
  for (let i = 0; i < arr.length - 1; i++) {
    currentNode.left = null
    currentNode.right = new TreeNode(arr[i + 1])
    currentNode = currentNode.right
  }
  return res
}
Copy the code

Original in nuggets: juejin.cn/post/684490…