使用JavaScript完成。给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。示例:输入:root = [1,null,2,3] 输出:[3,2,1]
时间: 2024-03-05 18:48:00 浏览: 25
好的,以下是使用JavaScript完成二叉树后序遍历的代码:
```javascript
function postorderTraversal(root) {
let result = [];
if (root === null) {
return result;
}
let stack = [root];
while (stack.length) {
let node = stack.pop();
result.unshift(node.val);
if (node.left !== null) {
stack.push(node.left);
}
if (node.right !== null) {
stack.push(node.right);
}
}
return result;
}
```
这里使用了一个栈来存储待处理的节点。首先将根节点入栈,然后在每一次循环中弹出栈顶节点,并将其值插入结果数组的开头。接着,将左右子节点(如果存在)分别推入栈中。由于后序遍历是先访问左右子节点,最后才访问根节点,因此需要先将根节点的值插入结果数组的开头。最后返回结果数组即可。
希望这个代码对您有帮助!
相关问题
使用kotlin完成题目:给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
以下是使用 Kotlin 实现二叉树的后序遍历的代码:
```kotlin
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun postorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
if (root == null) {
return result
}
result.addAll(postorderTraversal(root.left))
result.addAll(postorderTraversal(root.right))
result.add(root.`val`)
return result
}
```
在这个实现中,我们首先检查根节点是否为空,若为空则返回一个空的结果列表。如果根节点不为空,则递归遍历其左子树和右子树,并将结果依次添加到结果列表中,最后再将根节点的值添加到结果列表中。这样就完成了二叉树的后序遍历。
已知二叉树的后序遍历序列:JGDHEBKLIFCA 中序遍历序列: DJGBEHACKILF 画出这棵二叉树的形态
根据已知的中序遍历序列和后序遍历序列,可以重构出这棵二叉树,具体过程如下:
1. 后序遍历序列的最后一个元素是根节点,即C是根节点。
2. 在中序遍历序列中找到根节点C的位置,C前面的是左子树节点,C后面的是右子树节点。
3. 在后序遍历序列中找到左子树的节点,即JGDHEBKLIF,这些节点是在C的左侧的。
4. 将JGDHEBKLIF拆分成两部分,前半部分JGDHEBK是左子树的后序遍历序列,后半部分LIF是右子树的后序遍历序列。
5. 对于左子树,其中序遍历序列为DJGBEHACK,再按照步骤1-4重构左子树;对于右子树,其中序遍历序列为ILF,重构右子树。
6. 将左右子树连到C上,得到完整的二叉树。
以下是重构后的二叉树形态:
```
C
/ \
/ \
/ \
/ \
J I
/ \ / \
G D L F
/ \ /
H E K
\
B
\
A
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)