二叉树的先序遍历(递归和非递归版本)-蒲公英云

二叉树的先序遍历(递归和非递归版本)

末蓝、 2022-05-09 05:22 257阅读 0赞

难易程度：★★

重要性：★★★★★

树结构是面试中的考察的重点，而树的遍历又是树结构的基础。

//先序遍历，递归版本
public static ArrayList<Integer> preOrder(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode tem = s.pop();// 根节点出栈
            // 把根节点加入结果集 前序遍历顺序：根、左，右 所以对应的进栈顺序为：右、左（根节点进栈后马上出栈了）
            res.add(tem.val);
            if (tem.right != null)
                s.push(tem.right);
            if (tem.left != null)
                s.push(tem.left);
        }
        return res;
    }
/**
     * 先序遍历，递归版本
     * @param root
     * @return
     */
    public static ArrayList<Integer> preOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<Integer>();
        preOrder(root,res);
        return res;
    }
    private static void preOrder(TreeNode root,ArrayList<Integer> res) {
        if(root==null)  return;
        res.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有