LeetCode 144. 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?

Subscribe to see which companies asked this question.

题目

给出一棵二叉树,返回其节点值的前序遍历。

分析

前序排序的非递归算法是相对简单的,只要使用栈,保证right,left的顺序

代码

方法一,非递归,运用一个栈即可

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> preorder = new ArrayList<Integer>();
        
        if (root == null) {
            return preorder;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            preorder.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
        return preorder;
    }
    
}

方法二: 递归遍历

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

Paste_Image.png

方法三 : 分治法

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        
        res.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);
        
        res.addAll(left);
        res.addAll(right);
        return res;
    }

Paste_Image.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

1534
来自专栏mathor

LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

 后序遍历的非递归代码得说一下,首先后序遍历得顺序是左右中,我们知道先序遍历的压栈顺序是先压右再压左,这样出来的顺序就是中左右,如果把先序遍历的压栈顺序稍微变一...

5743
来自专栏LeetCode

LeetCode 897. Increasing Order Search Tree

题目大意:将一个BST,转化为一个只有右孩子的树,并且,这个树从根节点到叶子节点是从小到大排列的。

2310
来自专栏赵俊的Java专栏

二叉树层序遍历为二维数组

2333
来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

741
来自专栏LeetCode

BST & AVL 二分搜索树 & 平衡二叉树的实现原理

本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

2701
来自专栏赵俊的Java专栏

二叉树的最大深度

2202
来自专栏Jack-Cui

111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2179
来自专栏Bingo的深度学习杂货店

Q100 Same Tree

Given two binary trees, write a function to check if they are the same or not. T...

3276
来自专栏赵俊的Java专栏

排序链表转换为二分查找树

2195

扫码关注云+社区

领取腾讯云代金券