LeetCode–重建二叉树

归子莫

发布于：2020年8月29日

LeetCode–重建二叉树

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

介绍

剑指 Offer 07. 重建二叉树

主站 105 题

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1 2	前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,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;
    }
}