欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有关二叉树框架

程序员文章站 2022-06-07 14:38:47
...

《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);//右
}

 

相关标签: 算法入门