二叉树的前序遍历

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);
    }
};