二叉树构造与变换

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build_from_post(inorder: list[int], postorder: list[int]):
    """Rebuild a tree with distinct values from its inorder and postorder walks (LC 106)."""
    pos = {v: i for i, v in enumerate(inorder)}  # value -> inorder index
    roots = reversed(postorder)  # backwards, postorder yields root, then right, then left

    def build(lo: int, hi: int):  # the subtree whose inorder range is [lo, hi)
        if lo == hi:
            return None
        root = TreeNode(next(roots))
        mid = pos[root.val]
        root.right = build(mid + 1, hi)  # right first, matching the reversed postorder
        root.left = build(lo, mid)
        return root

    return build(0, len(inorder))

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Rebuild a tree with distinct values from its inorder and postorder walks (LC 106).
TreeNode* buildFromPost(const vector<int>& inorder, const vector<int>& postorder) {
    unordered_map<int, int> pos;  // value -> inorder index
    for (int i = 0; i < (int)inorder.size(); i++) pos[inorder[i]] = i;
    int next = (int)postorder.size() - 1;  // backwards, postorder yields root, then right, then left
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {  // inorder range [lo, hi)
        if (lo == hi) return nullptr;
        TreeNode* root = new TreeNode(postorder[next--]);
        int mid = pos[root->val];
        root->right = build(mid + 1, hi);  // right first, matching the reversed postorder
        root->left = build(lo, mid);
        return root;
    };
    return build(0, inorder.size());
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private final Map<Integer, Integer> pos = new HashMap<>(); // value -> inorder index
    private int[] postorder;
    private int next;

    // Rebuild a tree with distinct values from its inorder and postorder walks (LC 106).
    TreeNode buildFromPost(int[] inorder, int[] postorder) {
        pos.clear();
        for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
        this.postorder = postorder;
        next = postorder.length - 1; // backwards, postorder yields root, then right, then left
        return build(0, inorder.length);
    }

    // The subtree whose inorder range is [lo, hi).
    private TreeNode build(int lo, int hi) {
        if (lo == hi) return null;
        TreeNode root = new TreeNode(postorder[next--]);
        int mid = pos.get(root.val);
        root.right = build(mid + 1, hi); // right first, matching the reversed postorder
        root.left = build(lo, mid);
        return root;
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// buildFromPost rebuilds a tree with distinct values from its inorder and postorder walks (LC 106).
func buildFromPost(inorder, postorder []int) *TreeNode {
	pos := map[int]int{} // value -> inorder index
	for i, v := range inorder {
		pos[v] = i
	}
	next := len(postorder) - 1 // backwards, postorder yields root, then right, then left
	var build func(lo, hi int) *TreeNode // the subtree whose inorder range is [lo, hi)
	build = func(lo, hi int) *TreeNode {
		if lo == hi {
			return nil
		}
		root := &TreeNode{Val: postorder[next]}
		next--
		mid := pos[root.Val]
		root.Right = build(mid+1, hi) // right first, matching the reversed postorder
		root.Left = build(lo, mid)
		return root
	}
	return build(0, len(inorder))
}

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_tree(nums: list[int]):
    """Maximum binary tree of distinct nums (LC 654), built in O(n)."""
    stack = []  # the right spine of the tree so far, values decreasing
    for x in nums:
        node = TreeNode(x)
        while stack and stack[-1].val < x:
            node.left = stack.pop()  # smaller nodes before x end up in its left subtree
        if stack:
            stack[-1].right = node  # x hangs right of the nearest larger value before it
        stack.append(node)
    return stack[0] if stack else None

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Maximum binary tree of distinct nums (LC 654), built in O(n).
TreeNode* maxTree(const vector<int>& nums) {
    vector<TreeNode*> stack;  // the right spine of the tree so far, values decreasing
    for (int x : nums) {
        TreeNode* node = new TreeNode(x);
        while (!stack.empty() && stack.back()->val < x) {
            node->left = stack.back();  // smaller nodes before x end up in its left subtree
            stack.pop_back();
        }
        if (!stack.empty()) stack.back()->right = node;  // x hangs right of the nearest larger value
        stack.push_back(node);
    }
    return stack.empty() ? nullptr : stack[0];
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Maximum binary tree of distinct nums (LC 654), built in O(n).
    TreeNode maxTree(int[] nums) {
        Deque<TreeNode> stack = new ArrayDeque<>(); // the right spine of the tree so far, values decreasing
        for (int x : nums) {
            TreeNode node = new TreeNode(x);
            while (!stack.isEmpty() && stack.peek().val < x)
                node.left = stack.pop(); // smaller nodes before x end up in its left subtree
            if (!stack.isEmpty()) stack.peek().right = node; // x hangs right of the nearest larger value
            stack.push(node);
        }
        return stack.isEmpty() ? null : stack.peekLast();
    }
}

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// maxTree builds the maximum binary tree of distinct nums (LC 654) in O(n).
func maxTree(nums []int) *TreeNode {
	var stack []*TreeNode // the right spine of the tree so far, values decreasing
	for _, x := range nums {
		node := &TreeNode{Val: x}
		for len(stack) > 0 && stack[len(stack)-1].Val < x {
			node.Left = stack[len(stack)-1] // smaller nodes before x end up in its left subtree
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 {
			stack[len(stack)-1].Right = node // x hangs right of the nearest larger value
		}
		stack = append(stack, node)
	}
	if len(stack) == 0 {
		return nil
	}
	return stack[0]
}