本文LeetCode(http://www.leetcode.com/onlinejudge)内的binary tree travel,包含3个:
1). Binary Tree Inorder Traversal
2). Binary Tree Level Order Traversal
3). Binary Tree Maximum Path Sum
1). Binary Tree Inorder Traversal
递归很简单;常规做法。非递归版本用stack保存,right,val,left依次压入。
class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> v; if (root == NULL) return v; travel(root->left, v); v.push_back(root->val); travel(root->right, v); return v; } void travel(TreeNode* cur, vector<int>& v) { if (cur == NULL) return; travel(cur->left, v); v.push_back(cur->val); travel(cur->right, v); } };
#include <stack> using namespace std; struct A { TreeNode* ptr; int val; A (TreeNode* p, int v=-1) : ptr(p), val(v) {} }; class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> v; if (root == NULL) return v; stack<A> q; q.push(A(root)); while (!q.empty()) { A cur = q.top(); q.pop(); if (cur.ptr == NULL) { v.push_back(cur.val); continue; } if (cur.ptr->right != NULL) q.push(A(cur.ptr->right)); q.push(A(NULL, cur.ptr->val)); if (cur.ptr->left != NULL) q.push(A(cur.ptr->left)); } return v; } };
2). Binary Tree Level Order Traversal
常规做法,队列实现
#include <queue> using namespace std; class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int> > res; if (root == NULL) return res; queue<TreeNode*> q; q.push(root); q.push(NULL); TreeNode* cur; vector<int> v; while (!q.empty()) { cur = q.front(); q.pop(); if (cur == NULL) { res.push_back(v); v.clear(); if (!q.empty()) q.push(NULL); continue; } v.push_back(cur->val); if (cur->left != NULL) q.push(cur->left); if (cur->right != NULL) q.push(cur->right); } return res; } };
3). Binary Tree Maximum Path Sum
方法:从叶节点开始向上搞。
#include <queue> using namespace std; class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int> > res; if (root == NULL) return res; queue<TreeNode*> q; q.push(root); q.push(NULL); TreeNode* cur; vector<int> v; while (!q.empty()) { cur = q.front(); q.pop(); if (cur == NULL) { res.push_back(v); v.clear(); if (!q.empty()) q.push(NULL); continue; } v.push_back(cur->val); if (cur->left != NULL) q.push(cur->left); if (cur->right != NULL) q.push(cur->right); } return res; } };
上面的code貌似贴错了。
update@2013/09/04
class Solution { public: int res ; int maxPathSum(TreeNode *root) { res = -111111; maxSum(root); return res; } int maxSum(TreeNode* cur) { if (cur == NULL) return 0; int left = max(maxSum(cur->left) , 0); int right = max(maxSum(cur->right), 0); int t = left + right + cur->val; res = (t > res ? t : res); t = max(left, right) + cur->val; return max(t, 0); } };
相关推荐
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段树 Range Sum Query - Mutable 排序 插入排序 Insertion Sort List 归并排序 Merge ...
2sum leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp ...invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - level_order_traversal.cpp - exponentiation_by_squaring.cpp - Maximum_Depth_B
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Leetcode-tree 94题 Binary Tree Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的方法最简单快捷。这道题是需要我们用Inorder的顺序输出节点。in...
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
102 Binary Tree Level Order Traversal.js(二叉树级订单Traversal.js) 103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和...
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
[104_maximum-depth-of-binary-tree.cpp] [105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-...
104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-...
https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level ...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...3sum 3sum_closest 4sum ...balance_binary_tree ...binary_tree_inorder_...binary_tree_level_order_traversal_I
java lru leetcode what_the_dead_men_say 所以这只是一个 repo,我从leetcode.com存储我的问题解决方案。 二叉树 0098 Validate Binary ...Tree ...Binary ...Maximum depth of binary tree - Java Iterative
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2.... Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary Tree