关于二叉树的定义,以及什么是二叉树的三种遍历(先序遍历,中序遍历,后序遍历),不是本文关注的重点,请自行查阅相关资料。本文的重点是如何用递归和迭代分别实现二叉树的三种遍历。
leetcode上有三道题分别求三种遍历结果:Binary Tree Preorder Traversal 、Binary Tree Inorder Traversal 、 Binary Tree Postorder Traversal
递归递归解法不用多说,只需在递归部分的不同位置将节点value置入数组即可:
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ function dfs(root, ans) { if (!root) return; // 先序 // ans.push(root.val); dfs(root.left, ans); // 中序 // ans.push(root.val); dfs(root.right, ans); // 后序 // ans.push(root.val); } var preorderTraversal = function(root) { var ans = []; dfs(root, ans); return ans; }; 迭代难点是迭代。
如果把二叉树看做图,那么二叉树的遍历其实就是图的深度优先遍历,而图的深度优先遍历能用手动模拟栈来解,那么二叉树的遍历也是可以的。
用栈模拟图的深度优先遍历,每次把父亲节点的儿子节点的一个入栈,并删除该儿子节点
当父亲节点的所有儿子节点都被删除时,父亲节点出栈
我们以下面一棵二叉树举例:
1 / \ 2 5 / \ 3 4如何用栈模拟遍历该二叉树?我们用 stack 数组模拟栈。
将root入栈。此时 stack = [1]
遍历root的子节点,将左子节点入栈。 stack = [1, 2]
此时栈顶元素为 2,开始遍历它的子节点。左子节点为 3, 入栈。 stack = [1, 2, 3]
此时栈顶元素为 3 ,它没有子节点,将它出栈。 stack = [1, 2]
此时栈顶元素为 2,遍历它的子节点。左子节点已经被遍历,于是右子节点,入栈。 stack = [1, 2, 4]
此时栈顶元素为 4,和 3 一样它也没有左右子节点,出栈。stack = [1, 2]
此时栈顶元素为 2 , 当父亲节点的所有儿子节点都被删除时,父亲节点出栈,于是它出栈。 stack = [1]
此时栈顶元素为 1,它的左子节点已经遍历,遍历右子节点,将 5 入栈。 stack = [1, 5]
此时栈顶元素为 5, 它没有子节点,出栈。 stack = [1]
此时栈顶元素为 1, 它的子节点都被遍历过了,出栈。 stack=[]
此时stack数组长度为0,迭代结束。
先序遍历
先序遍历只需按照如上的步骤模拟栈,在每次入栈的时候将节点的value值放入ans数组即可。
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function(root) { if (!root) return []; var stack = [] // 栈模拟 , ans = []; stack.push(root); ans.push(root.val); while (stack.length) { var elem = stack[stack.length - 1]; if (elem.left) { ans.push(elem.left.val); stack.push(elem.left); elem.left = null; } else if (elem.right) { ans.push(elem.right.val); stack.push(elem.right); elem.right = null; } else stack.pop(); } return ans; };还有一种更简洁的代码写法,因为二叉树父节点最多就两个子节点,所以直接遍历两个节点,然后在栈中删除父节点即可。
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function(root) { if (!root) return []; var stack = [] // 栈模拟 , ans = []; stack.push(root); while (stack.length) { var elem = stack.pop(); ans.push(elem.val); if (elem.right) stack.push(elem.right); if (elem.left) stack.push(elem.left); } return ans; };后序遍历