public List<Integer> inorderTraversal(TreeNode root) {
    	System.out.println("中序遍历");
        List<Integer> list = new ArrayList<Integer>();
        if(root!=null){
        	/**
        	 * 中序遍历,左头右的顺序,所以要先打印出最左边的子树,我们就先一直向左找
        	 * 直到为空,即到最左处的时候,出栈,此时的元素就是最左边的节点,打印后,寻找
        	 * 它的右子树,重复上述步骤.
        	 */
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(!stack.isEmpty() || root!=null){
                if(root!=null){
                    stack.push(root);
                    root = root.left;
                } else{
                    root = stack.pop();
                    list.add(root.val);
                    root = root.right;
                }
            }
        }
        return list;
    }

更多推荐