package main import "container/list" import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ func preorderTraversal( root *TreeNode ) []int { if root == nil { return nil } var ret []int var l list.List ret = append(ret, root.Val) if root.Right != nil { l.PushFront(root.Right) } if root.Left != nil { l.PushFront(root.Left) } for l.Len() > 0 { ele := l.Front() root := ele.Value.(*TreeNode) l.Remove(ele) ret = append(ret, root.Val) if root.Right != nil { l.PushFront(root.Right) } if root.Left != nil { l.PushFront(root.Left) } } return ret }
解题思路:
- 前序遍历,即先遍历父节点,再遍历左子节点,最后遍历右子节点。这里遍历左子节点时,是要求将左子节点以下的节点都遍历结束后,才对右子节点做相同的遍历操作。
- 上述的遍历操作符合深度优先搜索 DFS,代码非递归实现的话,可以选择栈作为辅助。
- 因为要求先遍历左子节点,所以入栈时需要将右子节点先入栈,再将左子节点入栈。
- Go 可以将 list.List 当作栈使用
方法二:递归
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector */ vector<int> preorderTraversal(TreeNode* root) { vector<int> res; preorder(root, res); return res; } void preorder(TreeNode *root, vector<int> &res) { if (root == nullptr) { return; } res.push_back(root->val); preorder(root->left, res); preorder(root->right, res); } };