题解 | #实现二叉树先序,中序和后序遍历#

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

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

import java.util.*;
import java.lang.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
     List<Integer> pre = new ArrayList<>();
    List<Integer> in = new ArrayList<>();
    List<Integer> post = new ArrayList<>();
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // 先序遍历
        preOrderRecur(root);
        // 中序遍历
        inOrderRecur(root);
        // 后序遍历
        postOrderRecur(root);
        int i = 0;
        int[][] res = new int[3][pre.size()];
        while(i < pre.size()){
            res[0][i] = pre.get(i);
            res[1][i] = in.get(i);
            res[2][i] = post.get(i);
            i++;
        }
        return res;
    }
    
    // 先序遍历非递归版
    public void preOrderRecur(TreeNode root){
        if(root!= null){
            Stack<TreeNode> stack = new Stack();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                pre.add(node.val);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);
                }
            }
        }
    }
    
    // 中序遍历非递归版
    public void inOrderRecur(TreeNode root){
        if(root!= null){
            Stack<TreeNode> stack = new Stack();
            while(!stack.isEmpty() || root != null){
                if(root!=null){
                    stack.add(root);
                    root = root.left;
                }else{
                    TreeNode node = stack.pop();
                    in.add(node.val);
                    if(node.right!=null){
                        root = node.right;
                    }
                }
            }
        }
    }
    
    // 后序遍历非递归版
     public void postOrderRecur(TreeNode root){
        if(root!= null){
            Stack<Integer> help =  new Stack();
            Stack<TreeNode> stack = new Stack();
            stack.add(root);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                help.add(node.val);
                if(node.left != null){
                    stack.add(node.left);
                }
                if(node.right != null){
                    stack.add(node.right);
                }
            }
            while(!help.isEmpty()){
                post.add(help.pop());
            }
        }
    }
    
    public void preOrderRecur1(TreeNode root){
            if(root == null){
                return;
            }
            pre.add(root.val);
            preOrderRecur(root.left);
            preOrderRecur(root.right);
    }
    
    public void inOrderRecur1(TreeNode root){
        if(root == null){
            return;
        }
        inOrderRecur(root.left);
        in.add(root.val);
        inOrderRecur(root.right);
    }
    
     public void postOrderRecur1(TreeNode root){
        if(root == null){
            return;
        }
        postOrderRecur(root.left);
        postOrderRecur(root.right);
         post.add(root.val);
    }
    
}
全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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