LeetCode–重建二叉树
<!-- more -->
博客阐明
文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！
介绍
剑指 Offer 07. 重建二叉树
主站 105 题
题目
输出某二叉树的前序遍历和中序遍历的后果，请重建该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7思路
- 应用前序遍历的第一个元素创立根节点。
- 创立一个栈，将根节点压入栈内。
- 初始化中序遍历下标为 0。
遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。
- 若上一个元素不等于中序遍历下标指向的元素，则将以后元素作为其上一个元素的左子节点，并将以后元素压入栈内。
- 若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后持续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则反复该操作，直至栈为空或者元素不相等。而后令以后元素为最初一个想等元素的右节点。
- 遍历完结，返回根节点
代码
/** * 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 == null || preorder.length == 0){ return null; } //前序遍历第一个为根节点 TreeNode root = new TreeNode(preorder[0]); int length = preorder.length; Stack<TreeNode> stack = new Stack<TreeNode>(); //将根节点压入栈 stack.push(root); int index = 0; for(int i = 1;i<length;i++){ int preorderVal = preorder[i]; //查看栈顶的对象 TreeNode node = stack.peek(); if(node.val != inorder[index]){ //判断中序遍历的对象是否为以后栈顶元素 node.left = new TreeNode(preorderVal); stack.push(node.left); }else{ while(!stack.isEmpty() && stack.peek().val == inorder[index]){ node = stack.pop(); index++; } node.right = new TreeNode(preorderVal); stack.push(node.right); } } return root; }}感激
Leetcode以及勤奋的本人