前序遍歷

前序遍歷首先訪問根結點然后遍歷左子樹，最后遍歷右子樹。
前序遍歷有個特點

• 節點的分布總是按照根節點 左子樹節點 右子樹節點 依次排列。

中序遍歷

中序遍歷首先遍歷左子樹，再訪問根節點，最后遍歷右子樹。
中序遍歷有個特點

• 根節點的左側是左子樹節點，右側是右子樹節點。

依靠前序遍歷和中序遍歷的特點構建二叉樹

leetcode 105
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

注意:
你可以假設樹中沒有重復的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：

3
/ \
9 20
/ \
15 7

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length==0 || inorder.length==0) return null;TreeNode root=new TreeNode(preorder[0]);for(int i=0;i<preorder.length;i++){if(preorder[0]==inorder[i]){root.left=buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));root.right=buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));break;}}return root;} }

總結

以上是生活随笔為你收集整理的从前序与中序遍历序列构造二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。