【每日阅读】2020年11月11日-从前序与中序遍历序列构造二叉树

真诚的希望您能留言与我交流,这会对我有非常大的帮助!

索引

链接

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

代码

树的思路其实挺简单,就是想明白处在根节点时该干什么,然后写成递归的处理每个节点就行。这道题就是不断找出子树的根节点,拼接到当前的根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
            return null;
        }

        int rootNum = preorder[0];

        // 根节点在中序遍历结果中的index
        int rootAtInOrderIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootNum) {
                rootAtInOrderIndex = i;
            }
        }

        TreeNode root = new TreeNode(rootNum);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootAtInOrderIndex + 1),
                Arrays.copyOfRange(inorder, 0, rootAtInOrderIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, rootAtInOrderIndex + 1, preorder.length),
                Arrays.copyOfRange(inorder, rootAtInOrderIndex + 1, inorder.length));

        return root;
    }
}

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2683

发表评论

登录后才能评论
GitHub
分享本页
返回顶部