leetcode-tree

2020-08-13

[toc]

Tree

108. 将有序数组转换为二叉搜索树

二叉搜索树的中序遍历就是一个有序数组，相当于是要根据中序遍历结果还原一棵二叉搜索树，代码如下：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }
    private TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        // 使用中间数字的右边数字作为根节点
        // int mid = (end - start + 1) / 2 + start;
        int mid = (end - start) /2 + start;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);
        return root;
    }
}

105. 从前序与中序遍历序列构造二叉树

前序遍历的第一个节点就是根节点，随后递归执行,可以通过构造中序遍历的字典来快速查找中序遍历根节点，优化时间

class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

恢复二叉搜索树

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        """
        1. 找到二叉搜索树中序遍历得到值序列的不满足条件的位置。
        2. 如果有两个，维护一个prednode, 用x保存, 第二个交换的位置使用Y保存
        以 1234 -> 1432 为例，当cur = 3时， x=4 y=cur=3 
                             当cur=2时，仅更新y值 y=cur=2  x非空，跳出循环
        """
        stack = list()
        pred = x = y = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                curnode = stack.pop()
                if pred and curnode.val < pred.val:
                    y = curnode
                    if not x:
                        x = pred
                    else:
                        break
                pred = curnode
                root = curnode.right
        
        x.val, y.val = y.val, x.val

BFS

模版

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

116. 填充每个节点的下一个右侧节点指针

O(1)空间解法

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node x = root;
        while (x.left != null) {
            Node head = x;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                // 模拟层次遍历，遍历右子树
                head = head.next;
            }
            x = x.left;
        }
        return root;
    }
}

O(n)空间解法
Bfs

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> Q = new LinkedList<Node>(); 
        Q.add(root);
        while (!Q.isEmpty()) {
            int size = Q.size();
            for (int i = 0;i < size;i++) {
                Node x = Q.poll();
                if (i < size - 1) {
                    x.next = Q.peek();
                }
                if (x.left != null) {
                    Q.offer(x.left);
                }
                if (x.right != null) {
                    Q.offer(x.right);
                }
            }
        }
        return root;
    }
}

103. 二叉树的锯齿形层次遍历

Bfs遍历这棵树，在指定位置翻转结果

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
        node_queue.offer(root);
        boolean is_left = true;
        while (!node_queue.isEmpty()) {
            LinkedList<Integer> array = new LinkedList<Integer>();
            int size = node_queue.size();
            for (int i =0;i < size;i++) {
                TreeNode node = node_queue.poll();
                if (node.left != null) {
                    node_queue.offer(node.left);
                }
                if (node.right != null) {
                    node_queue.offer(node.right);
                }
                if (is_left) {
                    array.add(node.val);
                } else {
                    array.push(node.val);
                }
            }
            is_left = !is_left;
            results.add(array);
        }
        
        return results;
    }
}

DFS

124. 二叉树中的最大路径和

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // 计算根节点最大收益
        int rootGain = maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 为负数则置0，不选择它，
        // 左子树最大收益
        int leftMax = Math.max(maxGain(root.left), 0);
        // 右子树最大收益
        int rightMax = Math.max(maxGain(root.right), 0);
        // 经过该节点的最大路径收益
        int gain = leftMax+rightMax + root.val;
        if (gain > maxSum) {
            maxSum = gain;
        }
        // 返回该节点的最大收益
        return root.val + Math.max(leftMax, rightMax);
    }
}