【算法】二叉树的四种遍历

vlambda
2022-04-30

【算法】二叉树的四种遍历

二叉树的四种遍历

分为「前序」、「中序」、「后序」、「层序」四种遍历。

【算法】二叉树的四种遍历

前序遍历

先序遍历是按照根节点 -> 左孩子 -> 右孩子的方式遍历，遍历结果是

1 2 4 5 3 6 7

中序遍历

中序序遍历是按照左孩子 -> 根节点 -> 右孩子的方式遍历，遍历结果为

4 2 51 6 3 7；

后序遍历

后序序遍历是按照左孩子 -> 右孩子 -> 根节点的方式遍历，遍历结果为

4 5 2 6 7 3 1；

层序遍历

层次遍历就是按照每一层从左向右的方式进行遍历，遍历结果为

1 2 3 4 5 6 7。

LeetCode算法题目--前序遍历

题目

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

给你二叉树的根节点 root ，返回它节点值的前序遍历。

【算法】二叉树的四种遍历

解答

根据前序遍历规则，先遍历根节点【result.push(node.val)】，在遍历左节点【preOrderTraverseNode(node.left)】，再遍历右节点【preOrderTraverseNode(node.right)】

/** * @param {TreeNode} root * @return {number[]} */var preorderTraversal = function(root) { let result = [] var preOrderTraverseNode = function(node){ if(node) { result.push(node.val) preOrderTraverseNode(node.left) preOrderTraverseNode(node.right) } } preOrderTraverseNode(root) return result};

LeetCode算法题目--后序遍历

题目

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

【算法】二叉树的四种遍历

解答

根据后序遍历规则，左孩子【postorderTraversal(node.left)】 -> 右孩子【postorderTraversal(node.right)】 -> 根节点【result.push(node.val)】

var postorderTraversal = function(root) {let result = [] var postorderTraversal = function(node){ if(node) { postorderTraversal(node.left) postorderTraversal(node.right) result.push(node.val) } } postorderTraversal(root) return result};

LeetCode算法题目--中序遍历

题目

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

给定一个二叉树的根节点 root ，返回它的中序遍历。

解答

根据中序遍历规则，左孩子【postorderTraversal(node.left)】 -> 根节点【result.push(node.val)】 -> 右孩子【postorderTraversal(node.right)】

/** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) { let result = [] var postorderTraversal = function(node){ if(node) { postorderTraversal(node.left) result.push(node.val) postorderTraversal(node.right) } } postorderTraversal(root) return result};

LeetCode算法题目--层序遍历

题目

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

解答

根据层序遍历规则，需要一层层去遍历，注意输出的是二维数组，空二叉树时候返回[], 定义返回值res，和数组队列queue。遍历每一层元素，并把每一层元素添加到res里。

/** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function(root) { if(root == null) return []; const queue = []; const res = []; queue.push(root); while (queue.length) { const arr = []; // 当前层元素 const n = queue.length; for(let i = 0; i < n; i++){ const node = queue.shift(); arr.push(node.val); if(node.left) queue.push(node.left); if(node.right) queue.push(node.right); } res.push(arr); } return res;};