中序遍历二叉树

二叉树中序遍历的规则:
(1)中序遍历左子树

(2)访问根节点

(3)中序遍历右子树
输入、输出描述
输入:
给定一个二叉树的根节点
输出:
返回中序遍历二叉树节点序列对应的”data"属性列表
Example
输入:
二叉树如下:
    1
   / \
   2  3
  /  / \
  4  5  6
输出:
4,2,1,5,3,6
代码:
import java.util.*;

public class Main {

    /**
    //该段代码仅用于调试,提交时请注释该段代码
    class TreeNode<T> {

        public T data;

        public TreeNode<T> left;

        public TreeNode<T> right;
    }
 */ 

 public int[] solution(TreeNode<Integer> root) {
		if (root == null) return new int[0];
   		List<Integer> res = new LinkedList<>();
   		LinkedList<TreeNode<Integer>> list = new LinkedList<>();
		 TreeNode<Integer> curt = root;
 	    while (curt != null || !list.isEmpty()) {
          while(curt != null) {
            list.addLast(curt);
            curt = curt.left;
          }
          curt = list.pollLast();
          res.add(curt.data);
          curt = curt.right;
      }
   	   int[] ret = new int[res.size()];
   		for (int i = 0; i < ret.length; i ++ ) {
  	        ret[i] = res.get(i);
   		}
   		return ret;
    }
}
一个创业中的苦逼程序员
评论专区

隐藏