题目描述

这里用到了二叉树的非递归中序遍历，说道这我把二叉树的前中后序遍历非递归也写一下把，也当自己复习了。

样例

class Solution {
    public TreeNode convert(TreeNode root) {
        if(root==null||root.left==null&&root.right==null)
        return root;
        TreeNode last=null;
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||root!=null){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                root=stack.pop();
                TreeNode cur=root;
                 cur.left=last;
                 if(last!=null)
                last.right=cur;
                 last=cur;
                root=root.right;
            }
        }
        TreeNode node=last;
        while(node!=null&&node.left!=null){
            node=node.left;
        }
        return node;
    }

}

算法1

(非递归遍历) $O(n^2)$

java 代码

//前序遍历非递归
public void preOrderUnRecur(TreeNode head){
    if(head!=null){
        Stack<TreeNode> stack=new Stack();
        stack.push(head);
        while(!stack.isEmpty()){
            head=stack.pop();
            System.out.print(head.val+" ");
            if(head.right!=null){
                stack.push(head.right);
            }
            if(head.left!=null){
                stack.push(head.left);
            }
        }
    }
}
//中序遍历
 public void inOrderUnRecur(TreeNode head){
     if(head!=null){
         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.print(head.val+" ");
                  head=head.right;
              }

          }
     }
 }
 //后序遍历
 public static void posOrderUnRecur1(TreeNode head) {
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().val + " ");
            }
        }
        System.out.println();
    }

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla