二叉树

1.二叉树的先序非递归遍历

• 定义一个栈并将根节点入栈
• 当栈不空的时候循环执行
  • 从栈中弹出一个结点，并访问它
  • 如果右孩子不空，右孩子入栈
  • 如果左孩子不空，左孩子入栈

public void preOrderUnCurpublic void preOrderUnCur(TreeNode root){
        if (root == null){
            System.out.println("这是个空树");
            return;
        }
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        System.out.println("");
    }

2.二叉树的中序非递归遍历

/**
 * 非递归中序遍历
 * 开始创建一个栈，创建一个指向根节点的变量
 * 当栈为空 && 当前结点为时 才结束循环，否则循环执行下面2句
 * 当前结点为空，从栈中弹出一个变成当前结点打印，并指向右孩子；
 * 当前结点不空，当前结点入栈，当前结点并指向左孩子‘
 * @param root 树根
 */
public void inOrderUnCur(TreeNode root){
    if (root == null){
        System.out.println("这是个空树");
        return;
    }
    Stack stack = new Stack<>();
    TreeNode p = root;
    while (!stack.isEmpty() || p != null){
        if(p != null){
            stack.push(p);
            p = p.left;
        }else{
            p = stack.pop();
            System.out.print(p.val + " ");
            p = p.right;
        }
    }
    System.out.println("");
}