LeetCode题解:Construct Binary Tree from Inorder and Postord

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

题解:通过中序遍历和后序遍历还原二叉树

解决思路:首先要明确一点,对于后序遍历的结果,如果一个元素所在的位置为i,若在中序遍历的i-1位置的元素为该元素的根结点,,说明该元素就是所在子树的右儿子(且没有子树),否则存在右子树。左子树倒没什么特别的

代码:

{private int inLen;private int postLen;public TreeNode buildTree(int[] inorder, int[] postorder) {inLen = inorder.length;postLen = postorder.length;return buildTree(inorder, postorder, null);}private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode root){if(postLen < 0){return null;}TreeNode node = new TreeNode(postorder[postLen–]);if(inorder[postLen] != node.val){node.right = buildTree(inorder, postorder, node);}inLen–;if((root == null) || inorder[inLen] != root.val){node.left = buildTree(inorder, postorder, node);}return node;}}

收敛自己的脾气,偶尔要刻意沉默,

LeetCode题解:Construct Binary Tree from Inorder and Postord

相关文章:

你感兴趣的文章:

标签云: