public List<List<Integer>> levelOrder(TreeNode root) {
        //返回的結(jié)果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(null == root){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //根節(jié)點(diǎn)入隊(duì)
        queue.add(root);
        while(!queue.isEmpty()){
            //一層的結(jié)果
            List<Integer> level = new ArrayList<Integer>();
            int levelCount = queue.size();
            //添加節(jié)點(diǎn)到一層的List中去
            for(int i = 0; i < levelCount ; i ++){
                //節(jié)點(diǎn)出隊(duì)
                TreeNode node = queue.remove();
                //節(jié)點(diǎn)的左子樹(shù)入隊(duì)
                if(node.left != null){
                  queue.add(node.left);   
                }
                //節(jié)點(diǎn)的右子樹(shù)入隊(duì)   
                if(node.right != null){
                  queue.add(node.right);   
                }  
                level.add(node.val);
            }
            res.add(level);
        }
        return res;
    }

public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root==null) {
			return res;
		}	
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//將根節(jié)點(diǎn)放入隊(duì)列中，然后不斷遍歷隊(duì)列
		queue.add(root);
		while(queue.size()>0) {
			//獲取當(dāng)前隊(duì)列的長(zhǎng)度，這個(gè)長(zhǎng)度相當(dāng)于 當(dāng)前這一層的節(jié)點(diǎn)個(gè)數(shù)
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//將隊(duì)列中的元素都拿出來(lái)(也就是獲取這一層的節(jié)點(diǎn))，放到臨時(shí)list中
			//如果節(jié)點(diǎn)的左/右子樹(shù)不為空，也放入隊(duì)列中
			for(int i=0;i<size;++i) {
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) {
					queue.add(t.left);
				}
				if(t.right!=null) {
					queue.add(t.right);
				}
			}
			//將臨時(shí)list加入最終返回結(jié)果中
			res.add(tmp);
		}
		return res;
}

public List<Integer> preorderTraversal(TreeNode root) {
        //遞歸
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    public void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
}

public List<Integer> inorderTraversal(TreeNode root) {
        //遞歸
        List<Integer> list = new LinkedList<>();
        inOrder(root,list);
        return list;
    }
    public void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
}

public List<Integer> postorderTraversal(TreeNode root) {
        //遞歸
        List<Integer> list = new LinkedList<>();
        postOrder(root,list);
        return list;
    }
    public void postOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
}

public List<Integer> preorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        //臨時(shí)節(jié)點(diǎn)，幫助遍歷二叉樹(shù)
        TreeNode node = root;
        //棧的作用是用來(lái)短暫的保存遍歷節(jié)點(diǎn)的值，以助于最后值的返回
        while(!stack.isEmpty() || node != null){
            while(node != null){
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
}

public List<Integer> inorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);//出棧的時(shí)候才將父節(jié)點(diǎn) 的值加入到結(jié)果中
            root = root.right;
        }
        return list;
}

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                list.addFirst(root.val);//addFirst():向鏈表首部添加元素
                root = root.right;
            } else {
                root = stack.pop();
                root = root.left;
            }
        }
        return list;
}

public static void morris(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        //cur有沒(méi)有左樹(shù)
        mostRight = cur.left;
        if(mostRight != null){//有左樹(shù)的情況
            //找到cur左樹(shù)上，真實(shí)的最右節(jié)點(diǎn)
            //前者說(shuō)明是第一次來(lái)到當(dāng)前的cur，后者說(shuō)明是第二次來(lái)到當(dāng)前的cur
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            //從while中出來(lái)，mostRight一定是cur左樹(shù)上的最右節(jié)點(diǎn)
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;//結(jié)束的是外層的循環(huán)?。。。。。。。。。。。?！
            }else{//走到這里意味著：mostRight.right == cur
                mostRight.right = null;
            }
        }
        //cur沒(méi)有左樹(shù)
        cur = cur.right;
    }
}

public static void morrisPre(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }else{
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println();
}

public static void morrisIn(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println();
}

public static void morrisPos(Node head) {
		if(head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while(cur != null) {
			mostRight = cur.left;
			if(mostRight != null) {
				while(mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if(mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				}else {
					mostRight.right = null;
					printEdge(cur.left);//逆序打印左樹(shù)的右邊界
				}
			}
			cur = cur.right;
		}
		printEdge(head);//最后打印整棵樹(shù)的右邊界
		System.out.println();
	}
 	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while(cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}
	private static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while(from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}