题目地址
https://leetcode.com/problems/binary-tree-preorder-traversal/description/
题目描述
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
思路
这道题目是前序遍历,这个和之前的leetcode 94 号问题 - 中序遍历
完全不一回事。
前序遍历是根左右
的顺序,注意是根
开始,那么就很简单。直接先将根节点入栈,然后
看有没有右节点,有则入栈,再看有没有左节点,有则入栈。 然后出栈一个元素,重复即可。
其他树的非递归遍历课没这么简单
关键点解析
-
二叉树的基本操作(遍历)
不同的遍历算法差异还是蛮大的
-
如果非递归的话利用栈来简化操作
-
如果数据规模不大的话,建议使用递归
-
递归的问题需要注意两点,一个是终止条件,一个如何缩小规模
-
终止条件,自然是当前这个元素是 null(链表也是一样)
-
由于二叉树本身就是一个递归结构, 每次处理一个子树其实就是缩小了规模,
难点在于如何合并结果,这里的合并结果其实就是mid.concat(left).concat(right)
,
mid 是一个具体的节点,left 和 right递归求出即可
代码
- 语言支持:JS,C++
JavaScript Code:
/* * @lc app=leetcode id=144 lang=javascript * * [144] Binary Tree Preorder Traversal * * https://leetcode.com/problems/binary-tree-preorder-traversal/description/ * * algorithms * Medium (50.36%) * Total Accepted: 314K * Total Submissions: 621.2K * Testcase Example: '[1,null,2,3]' * * Given a binary tree, return the preorder traversal of its nodes' values. * * Example: * * * Input: [1,null,2,3] * 1 * \ * 2 * / * 3 * * Output: [1,2,3] * * * Follow up: Recursive solution is trivial, could you do it iteratively? * */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function(root) { // 1. Recursive solution // if (!root) return []; // return [root.val].concat(preorderTraversal(root.left)).concat(preorderTraversal(root.right)); // 2. iterative solutuon if (!root) return []; const ret = []; const stack = [root]; let t = stack.pop(); while (t) { ret.push(t.val); if (t.right) { stack.push(t.right); } if (t.left) { stack.push(t.left); } t = stack.pop(); } return ret; };
C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; vector<TreeNode*> s; while (root != NULL || !s.empty()) { while (root != NULL) { v.push_back(root->val); s.push_back(root); root = root->left; } root = s.back()->right; s.pop_back(); } return v; } };LeetCode题解102.binary-tree-level-order-traversal
题目地址 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to…
LeetCode题解103.binary-tree-zigzag-level-order-traversal题目地址 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ 题目描述 和leetcode 102 基本是一样的,思路是完全一样的。 Given a binary tree, return the zigzag level order trav…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…
LeetCode题解1104.path-in-zigzag-labelled-binary-tree题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标…
LeetCode题解104.maximum-depth-of-binary-tree题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the lo…