树的遍历--递归思想（JavaScript）-白红宇

树的遍历--递归思想（JavaScript）

阅读量：3947 次

发布时间：2019-05-24

本文共 8764 字，大约阅读时间需要 29 分钟。

树的遍历--递归思想（JavaScript）

先序遍历

先序遍历(按照先访问根节点的顺序)

var preorderTraversal = function (root) {
   	const res = []	function traversal (root) {
   		if (root !== null) {
   			res.push(root.val) // 访问根节点的值			traversal(root.left) // 递归遍历左子树			traversal(root.right) // 递归遍历右子树		}	}	traversal(root)	return res}

中序遍历

中序遍历(按照根节点在中间访问的顺序)

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}

后序遍历

后序遍历(按照根节点在后间访问的顺序)

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}

相同的树

给定两个二叉树，编写一个函数来检验它们是否相同

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

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)}

翻转二叉树

翻转一颗二叉树

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)}

N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历

// 递归思想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}// 匿名函数var postorder = function (root) {
   	const res = []	;(function (root) {
   		if (root !== null) {
   			root.children.forEach(child => {
   				arguments.callee(child)			})			res.push(root.val)		}	})(root)	return res}// 栈思想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()}

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历

即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

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	}}// 优化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	}}

二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 K 个最小的元素

可以假设 k 总是有效的，1 <= k <= 二叉搜索树元素个数

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]}// 优化，减少遍历次数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]}// 进一步优化，使用 O(1) 的额外空间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}

二叉树的层序遍历

给一个二叉树，返回其按层序遍历得到的节点值

即逐层地，从左到右访问所有的节点

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}

二叉树的右视图

给一个二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

基本思路
- 先序遍历，记录每一层深度下的节点的值
- 先记录左节点再记录右节点
- 则最后记录的值即为该层深度的右视图看到的值

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.lenth; ++i) {
   		res.push(arr[i][arr[i].length - 1])	}	return res}

二叉树的最大深度

给定一个二叉树，找出其最大深度
- 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
- 叶子节点是指没有子节点的节点

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}

二叉树的层次遍历 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()}

二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为2或0

如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值

给出这样一个二叉树，需要输出所有节点中的第二小的值，如果第二小的值不存在的话，输出-1

var findSecondMinimumValue = function(root) {
     let arr = []  ;(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}

从二叉搜索树到更大的树

给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点node的新值等于原树中大于或等于node.val的值之和

二叉搜素树满足下列约束条件
- 节点的左子树仅包含键小于节点键的节点
- 节点的右子树仅包含键大于节点键的节点
- 左右子树也必须是二叉搜索树

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}

把二叉搜索树转换为累加树

给定一个二叉搜索树，把它转换成为累加树，使得每个节点的值是原来的节点值加上所有大于它的节点值之和

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}

二叉搜索树中的搜索

给定二叉搜索树的根节点和一个值

需要在二叉搜索树中找到节点值等于给定值的节点

返回以该节点为根的子树，如果节点不存在，则返回NULL

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)}

N叉树的最大深度

给定一个 N 叉树，找到其最大深度

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数

说明
- 树的深度不会超过1000
- 树的节点总不会超过5000

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  }}

N 叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历

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}

递增顺序查找树

给你一个树，请按中序遍历重新排列树，使树中最左边的节点现在是树的根，并且每个节点没有左子节点，只有一个右子节点

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}

转载地址：http://djqwi.baihongyu.com/

你可能感兴趣的文章

Putting it All Together: Wireframing the Example App 把APP例子用线框图圈起来

查看>>

Implementing Lateral Navigation 实现横向导航

查看>>

Implementing Ancestral Navigation 实现原始导航

查看>>

Implementing Temporal Navigation 实现时间导航

查看>>

Responding to Touch Events 响应触摸事件

查看>>