144.二叉树的前序遍历

题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 递归

递归的套路

递归三部曲

1.确定递归函数的参数和返回值
这一步需要从递归函数的作用推出递归函数需要的参数和返回值是什么。
2.确定终止条件
3.确定单层递归的逻辑

题解

思路：递归将大问题拆分成重复的小问题，所以需要忽略整体的流程，聚焦在某一个中间状态。

1. 确定递归函数的参数和返回值
   题目是返回一颗树的前序遍历数组，我们可以将参数设置为结果数组res。还需要当前指向的节点指针root，标记已经遍历到的位置。
   所以递归函数的作用可以抽象为：将当前节点root的值放入结果数组res中
   返回值就是结果集res。

var preorderTraversal = function(root,res){	return res;
}

2. 确定终止条件
   当遍历到叶子节点时，说明本次从上至下的递归已经结束，也就是一条路径遍历完毕。这个时候返回本次递归，状态会回到上一个状态。

if(root==null)return res;

3. 确定单层递归的逻辑
   
   假设此时在节点2的位置, 前序节点的处理顺序是:中 -> 左 -> 右

我们需要把节点2的值放入结果数组res中，然后在将节点2的左节点值放入数组res，最后将节点2的右节点值放入数组res。根据步骤1，我们知道递归函数的作用可以抽象为将当前节点root的值放入结果数组res中，所以节点2的左节点、右节点我们可以直接用递归来表示。

//前序遍历先处理节点
res.push(root.val);
//左
preorderTraversal(root.left,res);
//右
preorderTraversal(root.right,res);
return res;

代码

var preorderTraversal = function(root, res= []) {if(root==null)return res;res.push(root.val);preorderTraversal(root.left,res);preorderTraversal(root.right,res);return res;
};

94.二叉树的中序遍历 递归

题目

定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

根据144.前序遍历的题解，我们直接到第三步确定单层递归的逻辑

中序遍历的顺序是: 左->中->右，假设我们此时在节点2的位置。那么我们应该先将节点2的左孩子节点值放入数组之后，才将节点2的值放入数组，最后将节点2的右孩子节点值放入数组。

//中序遍历先走左子树
inorderTraversal(root.left,res);
//处理中间节点
res.push(root.val);
//右
preorderTraversal(root.right,res);
return res;

代码

var inorderTraversal = function(root,res=[]) {if(root==null)return res;inorderTraversal(root.left,res);res.push(root.val);inorderTraversal(root.right,res);return res;
};

总结

递归

//前序遍历
var preorderTraversal = function(root, res= []) {if(root==null)return res;res.push(root.val);//处理根节点preorderTraversal(root.left,res);//左preorderTraversal(root.right,res);//右return res;
};
//中序遍历
var inorderTraversal = function(root,res=[]) {if(root==null)return res;inorderTraversal(root.left,res);//左res.push(root.val);//处理根节点inorderTraversal(root.right,res);//右return res;
};
//后序遍历
var postorderTraversal = function(root,res=[]) {if(root==null)return res;postorderTraversal(root.left,res);//左postorderTraversal(root.right,res);//右res.push(root.val);return res;
};