转载

二叉树

二叉树的先序,中序,后序遍历

  • 知识点

    二叉树

    • 先序遍历:先根节点,之后左子树,后右子树 序列:ABDECFG

    • 中序遍历:先左子树,之后根节点,后右子树 序列:DBEAFCG

    • 后序遍历:先左子树,之后右子树, 后根节点 序列:DEBFGCA

  • 剑指offer题目

    • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

    • 思想:主要考递归思路,递归建立左右子树

      /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
      public class Solution {
          public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
              return digui(pre, 0, pre.length-1, in, 0, in.length-1);
          }
          //startP, endP代表先序序列的起始和结束位置
          //startI, endI代表中序序列的起始和结束位置
          public TreeNode digui(int[]pre, int startP, int endP, int[]in, int startI, int endI){
              if((startP > endP) || (startI > endI)) return null;
              TreeNode root = new TreeNode(pre[startP]);
              int index = 0;
              //在中序序列中找到根节点的位置
              for(int i = startI; i <= endI; i++) {
                  if(pre[startP] == in[i]) index = i;
              }
              //左子树
              root.left = digui(pre, startP+1, startP + index - startI, in, startI, index-1);
              //右子树
              root.right = digui(pre, startP+index-startI+1, endP, in, index+1, endI);
              assert ((endP-startP-index+startI-1) == (endI-index-1));
              return root;
          }
      }
      
正文到此结束
本文目录