搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 程序迷城 > 二叉树遍历(Java)

二叉树遍历(Java)

程序迷城 2020-06-29
01
前序遍历


public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if(null == root){
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        result.add(node.val);
        if(node.right != null){
            stack.push(node.right);
        }
        if(node.left != null){
            stack.push(node.left);
        }
    }

    return result;
}


02
中序遍历


public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if(null == root){
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while(!stack.isEmpty() || cur != null){

        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }

        TreeNode node = stack.pop();
        if(node.right != null){
            cur = node.right;
        }

        result.add(node.val);
    }

    return result;
}


03
后序遍历


public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.addFirst(node.val);
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    return output;
}


04
遍历

参考:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

例子:后序遍历

根据调整左右节点和自身节点入栈对顺序(标红代码)可以轻松实现前、中、后序遍历


public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if(null == root){
        return result;
    }

    Stack<Object> stack = new Stack<>();
    stack.push(root);

    while(!stack.isEmpty()){
        Object obj = stack.pop();
        if(null == obj){
            continue;
        }
        if(obj instanceof TreeNode){
            TreeNode node = (TreeNode)obj;
            stack.push(node.val);
            stack.push(node.right);
            stack.push(node.left);

        }else{
            result.add((Integer)obj);
        }
    }

    return result;
}




长按上图,识别图中二维码之后即可关注。





版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《二叉树遍历(Java)》的版权归原作者「程序迷城」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注程序迷城微信公众号

程序迷城微信公众号:gh_20f03a48135e

程序迷城

手机扫描上方二维码即可关注程序迷城微信公众号

程序迷城最新文章

精品公众号随机推荐