二叉树的前序遍历（递归和非递归）

Bertha 。 2022-06-06 01:14 263阅读 0赞

上一篇是后续遍历，这一篇记录一下前序遍历，递归代码如下：

ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        pre(root);
        return list;
    }
    private void pre(TreeNode root){
        if(root == null)
            return;
        list.add(root.val);
        pre(root.left);
        pre(root.right);
    }

非递归的情况是用一个栈记录当前访问的节点的左右节点，右节点先入栈，左节点后入栈，这样出栈的时候顺序才是正确的。
非递归代码：

ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> preorderTraversal(TreeNode root) { 
        if(root == null)
            return list;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode temp = s.pop();
            list.add(temp.val);
            if(temp.right != null){
                s.push(temp.right);
            }
            if(temp.left != null){
                s.push(temp.left);
            }
        }
        return list;
    }