初级数据结构,大佬可以忽略滴~
二叉树的前中后序
很长一段时间我都是通过死记硬背的方法来记二叉树的 前、中、后 序遍历的,但是久了不用就老是忘,忘了又去翻,效率非常的低下,后面看了有位大佬的博客(忘记是哪一篇了,就直接贴大佬的github主页了),保持先左后右的循序,前中后实际上就是指根背遍历到的位置,也就是说:
- 前序遍历是指根在前:根 -> 左 -> 右
- 中序遍历... 根在中:左 -> 根 -> 右
- 后序...根在后:左 -> 右 -> 根
递归法
理解了上面的记忆方法,再来结合递归遍历可以轻松的写出树的前中后遍历。
前序遍历: 先打印出根节点,然后递归左子树,最后递归右子树
/**
* 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 {number[]}
*/
var preorderTraversal = function(root) {
if(!root) return []
let arr = []
const readTree = (tree) => {
if(!tree) return
arr.push(tree.val)
readTree(tree.left)
readTree(tree.right)
}
readTree(root)
return arr // 最终遍历的结果
};
中序遍历: 先递归左子树,然后打印根节点,最后递归右子树
/**
* 数据结构同
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
if(!root) return []
let arr = []
const readTree = (tree) => {
if(!tree) return
readTree(tree.left)
arr.push(tree.val)
readTree(tree.right)
}
readTree(root)
return arr // 最终遍历的结果
};
后序遍历: 先递归左子树,然后递归右子树,后打印根节点
/**
* 数据结构同
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
if(!root) return []
let arr = []
const readTree = (tree) => {
if(!tree) return
readTree(tree.left)
readTree(tree.right)
arr.push(tree.val)
}
readTree(root)
return arr // 最终遍历的结果
};
结合此方法,以后遇到二叉树的遍历,再也不用怕啦~