
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

2、前序遍历

先根节点，再左子树，再右子树。

递归前序遍历：


public void preorderTraversal(TreeNode root) {
    if (root!=null){
        System.out.print(root.val);//根
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}

非递归前序遍历：


    /**
     *@MethodName preorderTraversal
     *@Description TODO 144. 二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        TreeNode now=root;
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (!stack.empty()||now!=null) {
            //访问当前元素，然后一直向左走，直到当前节点为null，就出栈其双亲
            if (now!=null){
                result.add(now.val);
                stack.push(now);
                now=now.left;
            }else {
                //栈顶元素出栈，确定其右子树情况
                now=stack.pop().right;
            }
        }
        return result;
    }

3、中序遍历

先左子树，再根节点，再右子树。

递归中序遍历：


public void inorderTraversal(TreeNode root) {
    if (root!=null){
        inorderTraversal(root.left);
        System.out.print(root.val);//根
        inorderTraversal(root.right);
    }
}

非递归中序遍历：


/**
     *@MethodName inorderTraversal
     *@Description TODO 94. 二叉树的中序遍历 https://leetcode.cn/problems/binary-tree-inorder-traversal/
     */
public List<Integer> inorderTraversal(TreeNode root) {
    TreeNode now=root;
    List<Integer> result=new ArrayList<>();
    Stack<TreeNode> stack=new Stack<>();
    while (!stack.empty()||now!=null) {
        //当前元素一致向左走，直到当前节点为null，就出栈其双亲
        if (now!=null){
            stack.push(now);
            now=now.left;
        }else {
            //栈顶元素出栈，并访问，确定其右子树情况
            TreeNode temp=stack.pop();
            result.add(temp.val);
            now=temp.right;
        }
    }
    return result;
}

前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。也就是说前序序列的出栈序列个数 $C^{2n}_n/(n+1)$ =其可能的不同二叉树个数。

4、后序遍历

先左子树，再右子树，再根节点。

递归中后序遍历：


public void postorderTraversal(TreeNode root) {
    if (root!=null){
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val);//根
    }
}

非递归后序遍历：


/**
     *@MethodName postorderTraversal
     *@Description TODO 145. 二叉树的后序遍历 https://leetcode.cn/problems/binary-tree-postorder-traversal/
     */
public List<Integer> postorderTraversal(TreeNode root) {
    //r 上次访问的对象
    TreeNode now=root,r=null;
    List<Integer> result=new ArrayList<>();
    Stack<TreeNode> stack=new Stack<>();
    while (!stack.empty()||now!=null) {
        //当前元素一直向左走，直到当前节点为null，就找其双亲右孩子
        if (now!=null){
            stack.push(now);
            now=now.left;
        }else {
            //栈顶元素不出栈，确定其右子树情况,
            //如果右子树为空，则出栈并访问；
            //如果右子树刚被访问过说明其左子树之前已进栈、并再出栈被访问了，此时左右子树都被访问，则出栈并访问
            now=stack.peek();
            if (now.right!=null&&now.right!=r){
                now=now.right;
            }else {
                //出栈、访问
                result.add(stack.pop().val);
                //记录
                r=now;
                now=null;
            }
        }
    }
    return result;
}

5、层次遍历

使用队列


/**
     *@MethodName levelOrder
     *@Description TODO 102. 二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
 
        int count=1;//每行节点的双亲数
        if(root!=null){
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            List<Integer> temp=new ArrayList<>();
            for (int i = 0; i < count; i++) {
                TreeNode head=queue.remove();
                temp.add(head.val);
                if (head.left!=null){
                    queue.add(head.left);
                }
                if (head.right!=null){
                    queue.add(head.right);
                }
            }
            result.add(temp);
            count=queue.size();
        }
        return result;
    }

三、由遍历序列构造二叉树

1、从前序与中序遍历序列构造二叉树

非递归：


 
    /**
     *@MethodName buildTree
     *@Description TODO 105. 从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
 
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root=new TreeNode(preorder[0]);
        //用栈存储未确定右孩子的节点
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        int index=0;//中序 的指针，从左往右扫描元素的顺序 恰好是 前序做到最左端后的回序迭代。
 
        //流程：识别左孩子->入栈，直到没有左孩子，按一步步迭代回去 出栈 找右孩子 再迭代
        //从左开始扫描前序，如果一个节点不是它前一个结点的左孩子，那一定是它前面某个结点的右孩子（因为前面所有结点都确定了左孩子）
        //  且一定是离它最近的有右孩子的结点。
        for (int i = 1; i < preorder.length; i++) {
            TreeNode parent = stack.peek();
 
            //根据当前扫描的中序的结点 和 前序是否相等，判断是否前序是否遍历到了当前最左端。
            if (preorder[i - 1] != inorder[index]) {//不相等表示没到最左端，要一直向左构建左子树,相等的那个也要构建进去、所以是i-1
                parent.left = new TreeNode(preorder[i]);
                stack.push(parent.left);
            } else {//相等表示到了最左端，而没有右节点出现前，中序顺序和前序的回溯即栈中顺序 相同
                //找到当前结点（前序到达最左端后的下一个结点，是栈中第一个有右节点的 结点的右节点 ）在中序中的位置
                while (!stack.empty() && stack.peek().val == inorder[index]) {
                    parent = stack.pop();
                    index++;
                }
                //找到后
                parent.right = new TreeNode(preorder[i]);
                stack.push(parent.right);
            }
        }
        return root;
    }

递归：


//left=0,riht=inorder.length-1,pos=0
public TreeNode buildTree(int[] preorder, int[] inorder, int left, int right ,int pos)｛
	if(pos>=preorder.lenth)
  	return null;
	if(left==right){
  	return new TreeNode(mid[left]);
  }
	TreeNode node=null;
	for(int i=left;i<=riht;i++){
  	if(preorder[pos]==inorder[i]);{
    	node=new TreeNode(inorder[i]);
    	node.left=buildTree(preorder,inorder,left,i-1,++pos);
    	node.right=buildTree(preorder,inorder,i+1,right,++pos);
    	break;
    }
	}
	return node;
｝

2、从中序与后序遍历序列构造二叉树

非递归：


    /**
     *@MethodName buildTree
     *@Description TODO 106. 从中序与后序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
 
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        int n=postorder.length;
        TreeNode root=new TreeNode(postorder[n-1]);
        //用栈存储未确定左孩子的节点
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        int index=n-1;//中序 的指针，从左往右扫描元素的顺序 恰好是 前序做到最左端后的回序迭代。
 
        //流程：向右检索 识别右孩子->入栈，直到没有右孩子，按一步步迭代回去 出栈 找左孩子 入栈再迭代
        //从右开始扫描后序，如果一个节点不是它后一个结点的右孩子，那一定是它前面某个结点的左孩子（因为前面所有结点都确定了右孩子）
        //  且一定是离它最近的有左孩子的结点。
        for (int i = n-2; i >=0; i--) {
            TreeNode parent = stack.peek();
 
            //根据当前扫描的中序的结点 和 后序是否相等，判断是否前序是否遍历到了当前最左端。
            if (postorder[i+1] != inorder[index]) {//不相等表示没到最右端，要一直向右构建左子树,相等的那个也要构建进去、所以是i+1
                parent.right = new TreeNode(postorder[i]);
                stack.push(parent.right);
            } else {//相等表示到了最右端，而没有左节点出现前，中序顺序和后序的回溯即栈中顺序 相同
                //找到当前结点（后序从右向左扫描到达最右端后的下一个结点，是栈中第一个有左节点的 结点的左节点 ）在中序中的位置
                while (!stack.empty() && stack.peek().val == inorder[index]) {
                    parent = stack.pop();
                    index--;
                }
                //找到后
                parent.left = new TreeNode(postorder[i]);
                stack.push(parent.left);
            }
        }
        return root;
    }

递归：


//left=0,riht=inorder.length-1,pos=postorder.length
public TreeNode buildTree(int[] postorder, int[] inorder, int left, int right ,int pos)｛
	if(pos<0)
  	return null;
	if(left==right){
  	return new TreeNode(mid[left]);
  }
	TreeNode node=null;
	for(int i=right;i>=left;i--){
  	if(preorder[pos]==inorder[i]);{
    	node=new TreeNode(inorder[i]);
    	node.left=buildTree(preorder,inorder,left,i-1,--pos);
    	node.right=buildTree(preorder,inorder,i+1,right,--pos);
    	break;
    }
	}
	return node;
｝

四、线索二叉树

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

n个结点的二叉树有n+1个空指针。利用这些空指针存放指向其前驱或后记的指针。

规定：若无左子树，令 lchild指向其前驱结点；若无右子树,.令rchild指向其后继结点。还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。

lchild

ltag（0表存储左孩子，1表前驱）

data

rtag（0表存储右孩子，1表后继）

rchild

引入线索二叉树生是为了加快查找结点前驱和后继的速度。

本文概念性描述及图示均来自王道考研数据结构一书

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/843662