湖北营销型网站建设费用,平面设计软件排行,网站开发报告书,北京网站排名推广1.递归
1.1 熟悉递归
所有的递归有两个基本特征#xff1a;
执行时范围不断缩小#xff0c;这样才能触底反弹。终止判断在调用递归的前面。
写递归的步骤#xff1a;
从小到大递推。分情况讨论#xff0c;明确结束条件。组合出完整方法。想验证就从大到小画图推演。
…1.递归
1.1 熟悉递归
所有的递归有两个基本特征
执行时范围不断缩小这样才能触底反弹。终止判断在调用递归的前面。
写递归的步骤
从小到大递推。分情况讨论明确结束条件。组合出完整方法。想验证就从大到小画图推演。
1.2 递归实现二叉树的前中后序遍历
/*** param {TreeNode} root* return {number[]}*/
var preorderTraversal function(root) {const nodeArray [];addNode(root, nodeArray);return nodeArray;
};function addNode(node, res) {if (!node) {return res;}// 前、中、后序遍历只需调换下面三行代码位置res.push(node.val); // 中addNode(node.left, res); // 左addNode(node.right, res); // 右
}2.迭代
2.1 迭代实现二叉树前中后序遍历
迭代主要是模拟一个系统栈出来将节点压入栈中再取出。前中序遍历容易理解后序遍历较为复杂涉及到反转操作。
前序遍历 */
/*** param {TreeNode} root* return {number[]}*/
var preorderTraversal function(root) {const nodeQueue [];if (!root) {return nodeQueue;}const nodeStack [];let treeNode root;while (nodeStack.length ! 0 || treeNode) {while (treeNode) {nodeQueue.push(treeNode.val);nodeStack.push(treeNode);treeNode treeNode.left;}treeNode nodeStack.pop();treeNode treeNode.right;}return nodeQueue;
};中序遍历
/*** param {TreeNode} root* return {number[]}*/
var inorderTraversal function(root) {const nodeQueue [];const nodeStack [];if (!root) {return nodeQueue;}let treeNode root;while (nodeStack.length ! 0 || treeNode) { while (treeNode) {nodeStack.push(treeNode);treeNode treeNode.left;}treeNode nodeStack.pop()nodeQueue.push(treeNode.val);treeNode treeNode.right;}return nodeQueue;
};
后序遍历 分析 观察后序遍历的结果是:1, 2, 3, 8, 9, 7, 6,如果将其反转的话就是6, 7, 9, 8, 3, 2, 1 反转后的后序遍历与前序遍历相比就是左右反了。前序遍历是中左右后序遍历是左右中只要调整前序遍历的左右顺序就可以得到后序遍历。 function postOrderTraversal(root) {const nodeQueue [];const nodeStack [];if (!root) {return nodeQueue;}let treeNode root;while (nodeStack.length ! 0 || treeNode) {while (treeNode) {nodeQueue.push(treeNode.val)nodeStack.push(treeNode);treeNode treeNode.right;}treeNode nodeStack.pop();treeNode treeNode.left();}nodeQueue.reverse(); // 将其进行反转return nodeQueue;
}
