数组遍历框架

线性迭代结构：

void traverse(int[] arr){
    for(int i=0; i<arr.length; ++i)
        // 迭代访问 arr[i]
}

++i和i++的效率有区别，前者直接返回i+1的结果，后者会生成一个临时变量，因此性能比前者较弱。

链表遍历框架

兼具迭代和递归：

// 基本的单链表节点
class ListNode{
    int val;
    ListNode next;
}

void traverse(ListNode head){
    for(ListNode p = head; p != null; p = p.next){
        // 迭代访问p.val
    }
}

void traverse(ListNode head){
    // 递归访问head.val
    traverse(head.next);
}

二叉树遍历

非线性递归遍历结构：

// 基本的二叉树结点
class TreeNode{
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root){
    traverse(root.left);
    traverse(root.right);
}

扩展到$n$叉树：

// 基本的n叉树结点
class TreeNode{
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root){
    for(auto && child : root.children)
        traverse(child);
}

求二叉树中最大路径和

LeetCode-124，hard——求二叉树中最大路径和（后序遍历）：

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入：[1, 2, 3]

1
/ \
2 3

输出：6

示例 2：

输入：[-10, 9, 20, null, null, 15, 7]

-10
/ \
9 20
/ \
15 7

输出：42

class Solution {
public:
    int ans =INT_MIN;
    int maxPathSum(TreeNode* root) {
        oneSideMax(root);
        return ans;
    }
    
    int oneSideMax(TreeNode* root){
        if(root == nullptr) return 0;
        int left = max(0, oneSideMax(root->left));	// 先访问左子树
        int right = max(0, oneSideMax(root->right));	// 再访问右子树
        ans = max(ans, left+right+root->val);	// 比较根结点
        return max(left,right)+root->val;
    }
};

重建二叉树

LeetCode-105，medium——根据前序遍历序列和中序遍历序列还原一棵二叉树（前序遍历）：

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

例如，给出

前序遍历 preorder = [3, 9, 20, 15, 7]
中序遍历 inorder = [9, 3, 15, 20, 7]
返回如下的二叉树：

3

/ \
9 20
/ \
15 7

限制：

0 <= 节点个数 <= 5000

TreeNode buildTree(int[] preoeder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap){
    if(preStart > preEnd || inStart > inEnd) return null;
    
    TreeNode root = new TreeNode(preorder[preStart]);	// 前序遍历第一个结点是根结点
    int inRoot = inMap.get(root.val);	// 获取中序遍历中根结点的索引
    int numsLeft = inRoot - inStart;	// 计算左子树的个数
    
    root.left = buildTree(preorder, preStart+1, preStart + numsLeft, inorder, inStart, inRoot-1, inMap);	// 递归构建左子树
    root.right = buildTree(preorder, preStart+numsLeft+1, preEnd, inorder, inRoot+1, inEnd, inMap);
  
    return root;
}

恢复一棵 BST

LeetCode-99，hard——根据前序遍历序列和中序遍历序列还原一棵二叉树（中序遍历）

二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

示例 1：

输入：[1, 3, null, null, 2]

1
/
3
\
2

输出：[3, 1, null, null, 2]

3
/
1
\
2

示例 2：

输入：[3, 1, 4, null, null, 2]

3
/ \
1 4
/
2

输出：[2, 1, 4, null, null, 3]

2
/ \
1 4
/
3

进阶：

使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

思路

二叉排序树的中序遍历序列是有序的，可以将该序列存放于一个数组。遍历该数组，找到顺序不一致的两个下标i和j，将arr[i].val和arr[j].val的值互换一下即可。

void traverse(TreeNide* node){
    if(!node) return;
    traverse(node->left);
    if(node->val < prev->val){
        s=(s==NULL)?prev:s;
        t=node;
    }
    prev=node;
    traverse(node->right);
}