算法系列——Binary Tree Preorder Traversal

题目描述

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

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].

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

解题思路

递归法

非常简单，注意递归函数的调用顺序，先输出根节点，然后是递归输出左子树，递归输出右子树。

非递归法

递归的实现在计算机内部还是栈结构，因此我们可以利用栈这种数据结构来进行二叉树的遍历。

图1

我们可以模拟系统栈对于递归过程的实现。对于图1中的简单二叉树，遍历时，系统依次将指令入栈。输出1（cout1），然后进入递归左子树过程(go 1-L)，继续执行指令，cout 2 go 2-L go 2-R ，执行完毕，出栈，再进入递归右子树过程(go 1-R)，执行cout 3 go 3-L go 3-R 执行完毕。

我们可以采用一个命令将结点和自身要进行的操作 进行绑定，代码如下：

程序实现

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> result=new ArrayList<Integer>();
         if(root==null)
            return result;
        Stack<Command> stack=new Stack<Command>();
        stack.push(new Command("go",root));
        while(!stack.isEmpty()){
            Command command=stack.pop();
            if("print".equals(command.s))
                result.add(command.node.val);
            else{
            //先进右孩子
                if(command.node.right!=null)
                    stack.push(new Command("go",command.node.right));
                    //再进左孩子
                if(command.node.left!=null)
                    stack.push(new Command("go",command.node.left));
               //再进自身
                stack.push(new Command("print",command.node));
            }

        }
        return result;
    }
}
class Command{
    String s;
    TreeNode node;
    Command(String s,TreeNode node){
        this.s=s;
        this.node=node;
    }
}

我们可以很容易将这种方式推广到二叉树中序和后续遍历过程，只需要调整结点自身的入栈顺序，即可。