做网站用的产品展示横幅,手机app开发技术,999免费网站传奇,姐妹直播视频tv二叉树的前序中序后序遍历-含递归和迭代代码 前序(中左右)中序(左中右)后序(左右中) 前序(中左右) 对于二叉树中的任意一个节点#xff0c;先打印该节点#xff0c;然后是它的左子树#xff0c;最后右子树 A-B-D-E-C-F //递归
const preorderTraversal (root) {const… 二叉树的前序中序后序遍历-含递归和迭代代码 前序(中左右)中序(左中右)后序(左右中) 前序(中左右) 对于二叉树中的任意一个节点先打印该节点然后是它的左子树最后右子树 A-B-D-E-C-F //递归
const preorderTraversal (root) {const res [];const preOrder (root) {if (root null) return;res.push(root.val);preOrder(root.left);preOrder(root.right);};preOrder(root);return res;
}//迭代利用栈特性后进先出 我们常用的循环其实就是迭代比如for,while,do ... while...循环等都属于迭代。
const preorderTraversal (root) {var res [];if(!root) return res;var stack [root];while(stack.length ! 0){var node stack.pop();res.push(node.val);if(node.right){stack.push(node.right);}if(node.left){stack.push(node.left);}}return res;
};中序(左中右) 对于二叉树中的任意一个节点先打印它的左子树然后是该节点最后右子树 D-B-E-A-C-F //递归
const inorderTraversal (root) {const res [];const inorder (root) {if (root null) {return;}inorder(root.left); // 先递归左子树res.push(root.val); // 将当前节点值推入resinorder(root.right); // 再递归右子树};inorder(root);return res;
};//迭代
const inorderTraversal (root) {const res [];const stack [];while (root) { // 能压栈的左子节点都压进来stack.push(root);root root.left;}while (stack.length) {let node stack.pop(); // 栈顶的节点出栈res.push(node.val); // 在压入右子树之前处理它的数值部分因为中序遍历node node.right; // 获取它的右子树while (node) { // 右子树存在执行while循环 stack.push(node); // 压入当前rootnode node.left; // 不断压入左子节点}}return res;
};
后序(左右中) 对于二叉树中的任意一个节点先打印它的左子树然后是右子树最后该节点 D-E-B-F-C-A
// 递归
const postorderTraversal (root) {let result []var postOrder (node) {if(node) {// 先遍历左子树postOrder (node.left)// 再遍历右子树postOrder (node.right)// 最后根节点result.push(node.val)}}postOrder(root)return result
};//迭代
//思路
//后序遍历与前序遍历不同的是
//后序遍历是左右根
//而前序遍历是根左右
//如果我们把前序遍历的 res.push(node.val) 变更为 res.unshift(node.val) 遍历结果逆序那么遍历顺序就由 根左右 变更为 右左根
//然后我们仅需将 右左根 变更为 左右根 即可完成后序遍历const postorderTraversal (root) {var res [];if(!root) return res;var stack [root];while(stack.length ! 0){var node stack.pop();// 根左右右左根res.unshift(node.val);// 先进栈左子树后右子树// 出栈的顺序就变更为先右后左// 右先头插法入list// 左再头插法入list// 实现右左根左右根if(node.left){stack.push(node.left);}if(node.right){stack.push(node.right);}}return res;
}
