Lintcode66 Binary Tree Preorder Traversal solution 题解

显示全部楼层 · 2017-11-3 00:01:00

【题目描述】
Given a binary tree, return the preorder traversal of its nodes' values.
给出一棵二叉树，返回其节点值的前序遍历。
【题目链接】
www.lintcode.com/en/problem/binary-tree-preorder-traversal/
【题目解析】
递归
递归版很好理解，首先判断当前节点(根节点)是否为null，是则返回空vector，否则先返回当前节点的值，然后对当前节点的左节点递归，最后对当前节点的右节点递归。递归时对结果的处理方式不同可进一步细分为遍历和分治两种方法。
分治
使用分治的方法和递归类似，但是不同的是递归是将结果作为参数传入递归函数中，而分治则是先将结果保留，随后再合并到最终结果中。
迭代
迭代时需要利用栈来保存遍历到的节点，首先进行出栈抛出当前节点，保存当前节点的值，随后将右、左节点分别入栈，迭代到其为叶子节点(NULL)为止。
【参考答案】
www.jiuzhang.com/solutions/binary-tree-preorder-traversal/