====== 差别 ======
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
教程_算法_实现二叉树先序_中序和后序遍历 [2021/09/14 16:29] admin 创建 |
教程_算法_实现二叉树先序_中序和后序遍历 [2021/09/15 15:27] (当前版本) admin |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | <markdown> | + | |
| + | [\<\< 返回算法列表](教程/ | ||
| # 实现二叉树先序，中序和后序遍历 | # 实现二叉树先序，中序和后序遍历 | ||
| - | </markdown> | + | > 描述 |
| + | 分别按照二叉树先序，中序和后序打印所有的节点。 | ||
| + | |||
| + | > 示例1 | ||
| + | |||
| + | ``` | ||
| + | 输入： | ||
| + | {1,2,3} | ||
| + | |||
| + | 返回值： | ||
| + | [[1, | ||
| + | ``` | ||
| + | |||
| + | ## 解答 | ||
| + | 注意：先中后指的是跟的次序 | ||
| + | 1. 先(根)序遍历（根左右） | ||
| + | 2. 中(根)序遍历（左根右） | ||
| + | 3. 后(根)序遍历（左右根） | ||
| + | |||
| + | ```javascript | ||
| + | |||
| + | | ||
| + | this.val = x | ||
| + | this.left = null | ||
| + | this.right = null | ||
| + | } | ||
| + | |||
| + | |||
| + | function threeOrders( root ) { | ||
| + | // write code here | ||
| + | let preArr = [] | ||
| + | let midArr = [] | ||
| + | let postArr = [] | ||
| + | preOrder2(root) | ||
| + | midOrder(root) | ||
| + | postOrder(root) | ||
| + | function preOrder(root) { | ||
| + | if(!root) return | ||
| + | preArr.push(root.val) | ||
| + | preOrder(root.left) | ||
| + | |||
| + | preOrder(root.right) | ||
| + | } | ||
| + | |||
| + | //也可不使用递归 | ||
| + | function preOrder2(root) { | ||
| + | if(!root) return | ||
| + | let stack = [] | ||
| + | let p = root | ||
| + | stack.push(p) | ||
| + | while(stack.length | ||
| + | p = stack.pop() | ||
| + | preArr.push(p.val) | ||
| + | if(p.right) stack.push(p.right) | ||
| + | if(p.left) stack.push(p.left) | ||
| + | } | ||
| + | } | ||
| + | |||
| + | function midOrder(root) { | ||
| + | if(!root) return | ||
| + | |||
| + | midOrder(root.left) | ||
| + | midArr.push(root.val) | ||
| + | midOrder(root.right) | ||
| + | } | ||
| + | |||
| + | function postOrder(root) { | ||
| + | if(!root) return | ||
| + | postOrder(root.left) | ||
| + | postOrder(root.right) | ||
| + | postArr.push(root.val) | ||
| + | |||
| + | } | ||
| + | return [preArr, midArr, postArr] | ||
| + | } | ||
| + | |||
| + | ``` | ||
| + | |||
admin · 2021/09/14 16:29 · 教程_算法_实现二叉树先序_中序和后序遍历.1631608181.txt.gz
