关于java:LeetCode–重建二叉树

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

以及勤奋的本人