前序遍历——递归
/*** 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 postorderTraversal = function (root) {let res = []let bfs = (root)=>{if (!root) returnres.push(root.val)bfs(root.left)bfs(root.right) }bfs(root)return res
};
前序遍历——迭代
// 前序遍历
const preorderTraversal = (root) => {const list = [];const stack = [];// 当根节点不为空的时候，将根节点入栈if(root) stack.push(root)while(stack.length > 0) {const curNode = stack.pop()// 第一步的时候，先访问的是根节点list.push(curNode.val)// 我们先打印左子树，然后右子树// 所以先加入栈的是右子树，然后左子树if(curNode.right !== null) {stack.push(curNode.right)}if(curNode.left !== null) {stack.push(curNode.left)}}return list
}
中序遍历——递归
/*** 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 postorderTraversal = function (root) {let res = []let bfs = (root)=>{if (!root) returnbfs(root.left)res.push(root.val)bfs(root.right) }bfs(root)return res
};
中序遍历——迭代
// 中序遍历
const inorderTraversal = (root) => {let list = []let stack = []let node = rootwhile(node || stack.length) {// 遍历左子树while(node) {stack.push(node)node = node.left}node = stack.pop()list.push(node.val)node = node.right}return list
}
后序遍历——递归
/*** 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 postorderTraversal = function (root) {let res = []let bfs = (root)=>{if (!root) returnbfs(root.left)bfs(root.right)res.push(root.val)}bfs(root)return res
};
后序遍历——迭代
/*** 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 postorderTraversal = function (root) {let res = []let stack = []if (root) {stack.push(root)}while (stack.length) {// 根左右=>右左根let node = stack.pop()res.unshift(node.val)// 左子树先进栈，右子树后进栈// 出栈的顺序就变更为 先右 后左// 右先头插法入list// 左再头插法入list// 实现右左根=>左右根if (node.left != null) {stack.push(node.left)}if (node.right != null) {stack.push(node.right)}}return res
};