Tree - 144. Binary Tree Preorder Traversal

ppxai

发布于 2020-09-23 17:43:29

2750

发布于 2020-09-23 17:43:29

文章被收录于专栏：皮皮星球皮皮星球

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

思路：

二叉树的先序遍历，递归求解和迭代，迭代使用list容器的链表代替栈来做

代码：

go：

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// recursive
/*func preorderTraversal(root *TreeNode) []int {
    var res = make([]int, 0)
    recursive(root, &res)
    return res
}


func recursive(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }
    *res = append(*res, root.Val)
    recursive(root.Left, res)
    recursive(root.Right, res)
}
*/

// iterative
func preorderTraversal(node *TreeNode) []int {

    var res []int 
    var stack []*TreeNode
    
    for node != nil || len(stack) != 0 {
        for node != nil {
            res = append(res, node.Val)
            
            stack = append(stack, node)
            node = node.Left
        }
        
        if len(stack) != 0 {
            node = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            node = node.Right
        }
    }
    
    return res
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年12月11日，如有侵权请联系 cloudcommunity@tencent.com 删除

binary