2018/2/2 19:07:51当前位置推荐好文程序员浏览文章

题目输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 fun(pre, in, 0, pre.length,0 ,in.length -1 );    }    private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){        if(inLeftIndex > inRightIndex   || preLeftIndex  > preRightIndex){            return null;        }        TreeNode root = new TreeNode(pre[preLeftIndex]);        for(int i = inLeftIndex; i <= inRightIndex; i++){            if(in[i] == pre[preLeftIndex]){                root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );                root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);                break;            }        }        return root;    }}
思路:

二叉树的前序遍历和中序遍历

  • 前序遍历:先访问当前节点,然后以前序访问左子树,右子树。
  • 中序遍历:先以中序遍历左子树,接着访问当前节点,然后以中序遍历右子树。

所以前序遍历的特点为:前序遍历的每一个节点都是当前子树的根节点,同时,以中序遍历中该节点为边界,可以把中序遍历的结果分为左子树和右子树

  • 前序遍历序列{1,2,4,7,3,5,6,8}
  • 中序遍历序列{4,7,2,1,5,3,8,6}

前序遍历的第一个节点将中序遍历的结果分成了{4,7,2}和{5,3,8,6}两部分,他就是以1为根的左右两个子树的全部节点
然后接着将其子树按照上述方法进行拆分,就可以获得原始的树结构了。
注:此种解法要保证在树中无重复节点
几个需要注意的点:

  • 边界检查
  • 如过要想复原一颗二叉树,需要知道他的前/后序遍历+中序遍历 因为前序和后序本质上是一样的,只有应用两种性质不一致的方式才能复原二叉树。
网友评论