二叉树三序迭代遍历(Java)

实现二叉树先序,中序和后序遍历

http://www.nowcoder.com/questionTerminal/a9fec6c46a684ad5a3abd4e365a9d362

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int[][] res = new int[3][];
        res[0] = toIntArray(preorder(root));
        res[1] = toIntArray(inorder(root));
        res[2] = toIntArray(postorder(root));
        return res;
    }

    //将List转换为整型数组
    int[] toIntArray(List<Integer> list){
        int[] res = list.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }

    //preorder
    List<Integer> preorder(TreeNode root)
    {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stk.isEmpty()){
            while(cur != null){
                res.add(cur.val);
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            cur = cur.right;
        }
        return res;
    }

    //inorder
    List<Integer> inorder(TreeNode root)
    {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stk.isEmpty()){
            while(cur != null){
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }

    //postorder
    List<Integer> postorder(TreeNode root)
    {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stk.isEmpty()){
            while(cur != null){
                res.add(0, cur.val);
                stk.push(cur);
                cur = cur.right;
            }
            cur = stk.pop();
            cur = cur.left;
        }
        return res;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务