有关二叉树框架

《labuladong 的算法⼩抄》学习笔记

基本的二叉树框架

void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}

 

LeetCode 124 题，难度 Hard，让你求⼆叉树中最⼤路径和，主要代码如下： 

int ans = INT_MIN;
// 求二叉树中最长路径和 
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，让你根据前序遍历和中序遍历的结果还原⼀棵⼆叉树，很经典的问题吧，主要代码如下： 

//根据前序遍历和中序遍历的结果还原一棵二叉树 
TreeNode buildTree(int[] preorder, 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]); //1. 根 前序确定根 
    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;
}

MAP容器相关

https://blog.csdn.net/dujuancao11/article/details/105334200 

 

Map.get(root.val)

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