二叉树的中序遍历

使用栈

public static void print2(TreeNode head)
    {
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||head!=null)
        {
            if(head!=null)
            {
                stack.push(head);
                head=head.left;
            }else
            {
                head=stack.pop();
                System.out.println(head.val);
                head=head.right;
            }
        }
    }

使用mirros

public static void print(TreeNode head)
    {
        TreeNode cur1=null;
        while(head!=null)
        {
            cur1=head.left;
            if(cur1!=null)
            {
                while(cur1.right!=null&&cur1.right!=head)
                {
                    cur1=cur1.right;
                }
                if(cur1.right==null)
                {
                    cur1.right=head;
                    head=head.left;
                    continue;
                }
                if(cur1.right==head)
                {
                    cur1.right=null;
                }
            }
            System.out.println(head.val);
            head=head.right;
        }
    }

代码实现

使用到了栈，通过改写二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Stack;
class BSTIterator {

    private TreeNode head;
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
          this.head=root;
          this.stack=new Stack<>();
    }

    /** @return the next smallest number */
    public int next() {
          while(head!=null)
            {
                stack.push(head);
                head=head.left;
            }
            if(!stack.isEmpty())
            {
                head=stack.pop();
                int temp=head.val;
                head=head.right;
                return temp;
            }
            return -1;
    }

    /** @return whether we have a next smallest number */
   public boolean hasNext() {
            return head!=null||!stack.isEmpty();
        }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */