已解答 简单
相关标签
相关企业给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
func postorderTraversal(root *TreeNode) []int { var res []int bfs := []*TreeNode{root} for len(bfs) != 0 { popNode := bfs[len(bfs)-1] bfs = bfs[:len(bfs)-1] if popNode == nil { continue } res = append(res, popNode.Val) bfs = append(bfs, popNode.Left) bfs = append(bfs, popNode.Right) } i, j := 0, len(res)-1 for i < j { res[i], res[j] = res[j], res[i] i++ j-- } return res }
func postorderTraversalOne(root *TreeNode) []int { var res []int if root == nil { return res } res = append(res, postorderTraversal(root.Left)...) res = append(res, postorderTraversal(root.Right)...) res = append(res, root.Val) return res }
已解答 简单
相关标签
相关企业给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]示例 4：
输入：root = [1,2]
输出：[1,2]示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
func preorderTraversal(root *TreeNode) []int { bfs := []*TreeNode{root} var res []int for len(bfs) != 0 { popNode := bfs[len(bfs)-1] bfs = bfs[:len(bfs)-1] if popNode == nil { continue } res = append(res, popNode.Val) bfs = append(bfs, popNode.Right) bfs = append(bfs, popNode.Left) } return res }
func preorderTraversalOne(root *TreeNode) []int { var res []int if root == nil { return res } res = append(res, root.Val) res = append(res, preorderTraversal(root.Left)...) res = append(res, preorderTraversal(root.Right)...) return res }
已解答 简单
相关标签
相关企业给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
这里中序是用一个指针，来记录需要遍历的值， 因为中序是 左中右， 而正常的root ,第一个就是中，无法确定位置，所以 用了一个指针来记录位置， 当指针不为空时， 将树的左孩子依次压入 指针， 当指针为空时，将bfs里最后一个结点弹出， 记录结果，则将指针华向该点 的右孩子， 这里的条件 是指针与bfs不能同时为空， 如果都为空时，就是到底了 func inorderTraversal(root *TreeNode) []int { cur := root varbfs []*TreeNode varres []int for cur != nil || len(bfs) != 0 { if cur != nil { bfs = append(bfs, cur) cur = cur.Left } else { popNode := bfs[len(bfs)-1] bfs = bfs[:len(bfs)-1] res = append(res, popNode.Val) cur = popNode.Right } } return res } func inorderTraversal(root *TreeNode) []int { node := root var bfs []*TreeNode for node != nil { bfs = append(bfs, node) node = node.Left } var res []int for len(bfs) != 0 { popNode := bfs[len(bfs)-1] bfs = bfs[:len(bfs)-1] if popNode == nil { continue } res = append(res, popNode.Val) rightNode := popNode.Right for rightNode != nil { bfs = append(bfs, rightNode) rightNode = rightNode.Left } } return res } func inorderTraversalOne(root *TreeNode) []int { if root == nil { return []int{} } var res []int res = append(res, inorderTraversal(root.Left)...) res = append(res, root.Val) res = append(res, inorderTraversal(root.Right)...) return res } 标签：遍历,TreeNode,res,popNode,bfs,第十四天,二叉树,root,append From： https://www.cnblogs.com/suxinmian/p/18010040