Skip to content

Latest commit

 

History

History
734 lines (641 loc) · 18.4 KB

二叉树的递归遍历.md

File metadata and controls

734 lines (641 loc) · 18.4 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

一看就会，一写就废！

二叉树的递归遍历

算法公开课

《代码随想录》算法视频公开课：每次写递归都要靠直觉？ 这次带你学透二叉树的递归遍历！，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

这次我们要好好谈一谈递归，为什么很多同学看递归算法都是“一看就会，一写就废”。

主要是对递归不成体系，没有方法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。

本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了，我们确认了递归的三要素，接下来就来练练手：

以下以前序遍历为例：

  1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：
void traversal(TreeNode* cur, vector<int>& vec)
  1. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
if (cur == NULL) return;
  1. 确定单层递归的逻辑：前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：
vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

此时大家可以做一做leetcode上三道题目，分别是：

可能有同学感觉前后中序遍历的递归太简单了，要打迭代法（非递归），别急，我们明天打迭代法，打个通透！

其他语言版本

Java：

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

Python：

# 前序遍历-递归-LC144_二叉树的前序遍历
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def dfs(node):
            if node is None:
                return
            
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return res
# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def dfs(node):
            if node is None:
                return
            
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
        dfs(root)
        return res
# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def dfs(node):
            if node is None:
                return
            
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res

Go：

前序遍历:

func preorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
	if node == nil {
            return
	}
	res = append(res,node.Val)
	traversal(node.Left)
	traversal(node.Right)
    }
    traversal(root)
    return res
}

中序遍历:

func inorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
	if node == nil {
	    return
	}
	traversal(node.Left)
	res = append(res,node.Val)
	traversal(node.Right)
    }
    traversal(root)
    return res
}

后序遍历:

func postorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
	if node == nil {
	    return
	}
	traversal(node.Left)
	traversal(node.Right)
        res = append(res,node.Val)
    }
    traversal(root)
    return res
}

Javascript：

前序遍历：

var preorderTraversal = function(root) {
// 第一种
//  let res=[];
//  const dfs=function(root){
//      if(root===null)return ;
//      //先序遍历所以从父节点开始
//      res.push(root.val);
//      //递归左子树
//      dfs(root.left);
//      //递归右子树
//      dfs(root.right);
//  }
//  //只使用一个参数 使用闭包进行存储结果
//  dfs(root);
//  return res;
// 第二种
  return root
    ? [
        // 前序遍历：中左右
        root.val,
        // 递归左子树
        ...preorderTraversal(root.left),
        // 递归右子树
        ...preorderTraversal(root.right),
      ]
    : [];
};

中序遍历

var inorderTraversal = function(root) {
// 第一种

    // let res=[];
    // const dfs=function(root){
    //     if(root===null){
    //         return ;
    //     }
    //     dfs(root.left);
    //     res.push(root.val);
    //     dfs(root.right);
    // }
    // dfs(root);
    // return res;

// 第二种
  return root
    ? [
        // 中序遍历：左中右
        // 递归左子树
        ...inorderTraversal(root.left),
        root.val,
        // 递归右子树
        ...inorderTraversal(root.right),
      ]
    : [];
};

后序遍历

var postorderTraversal = function(root) {
    // 第一种
    // let res=[];
    // const dfs=function(root){
    //     if(root===null){
    //         return ;
    //     }
    //     dfs(root.left);
    //     dfs(root.right);
    //     res.push(root.val);
    // }
    // dfs(root);
    // return res;

  // 第二种
  // 后续遍历：左右中
  return root
    ? [
        // 递归左子树
        ...postorderTraversal(root.left),
        // 递归右子树
        ...postorderTraversal(root.right),
        root.val,
      ]
    : [];
};

TypeScript:

// 前序遍历
function preorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        res.push(node.val);
        traverse(node.left, res);
        traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

// 中序遍历
function inorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        traverse(node.left, res);
        res.push(node.val);
        traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

// 后序遍历
function postorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        traverse(node.left, res);
        traverse(node.right, res);
        res.push(node.val);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

C:

//前序遍历：
void preOrder(struct TreeNode* root, int* ret, int* returnSize) {
    if(root == NULL)
        return;
    ret[(*returnSize)++] = root->val;
    preOrder(root->left, ret, returnSize);
    preOrder(root->right, ret, returnSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preOrder(root, ret, returnSize);
    return ret;
}

//中序遍历：
void inOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node)
        return;
    inOrder(node->left, ret, returnSize);
    ret[(*returnSize)++] = node->val;
    inOrder(node->right, ret, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    inOrder(root, ret, returnSize);
    return ret;
}

//后序遍历：
void postOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(node == NULL) 
        return;
    postOrder(node->left, ret, returnSize);
    postOrder(node->right, ret, returnSize);
    ret[(*returnSize)++] = node->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret= (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    postOrder(root, ret, returnSize);
    return ret;
}

Swift:

前序遍历：（144.二叉树的前序遍历）

func preorderTraversal(_ root: TreeNode?) -> [Int] {
    var res = [Int]()
    preorder(root, res: &res)
    return res
}
func preorder(_ root: TreeNode?, res: inout [Int]) {
    if root == nil {
        return
    }
    res.append(root!.val)
    preorder(root!.left, res: &res)
    preorder(root!.right, res: &res)
}

中序遍历：（94. 二叉树的中序遍历）

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var res = [Int]()
    inorder(root, res: &res)
    return res
}
func inorder(_ root: TreeNode?, res: inout [Int]) {
    if root == nil {
        return
    }
    inorder(root!.left, res: &res)
    res.append(root!.val)
    inorder(root!.right, res: &res)
}

后序遍历：（145. 二叉树的后序遍历）

func postorderTraversal(_ root: TreeNode?) -> [Int] {
    var res = [Int]()
    postorder(root, res: &res)
    return res
}
func postorder(_ root: TreeNode?, res: inout [Int]) {
    if root == nil {
        return
    }
    postorder(root!.left, res: &res)
    postorder(root!.right, res: &res)
    res.append(root!.val)
}

Scala:

前序遍历：（144.二叉树的前序遍历）

object Solution {
  import scala.collection.mutable.ListBuffer
  def preorderTraversal(root: TreeNode): List[Int] = {
    val res = ListBuffer[Int]()
    def traversal(curNode: TreeNode): Unit = {
      if(curNode == null) return
      res.append(curNode.value)
      traversal(curNode.left)
      traversal(curNode.right)
    }
    traversal(root)
    res.toList
  }
}

中序遍历：（94. 二叉树的中序遍历）

object Solution {  
  import scala.collection.mutable.ListBuffer
  def inorderTraversal(root: TreeNode): List[Int] = {
    val res = ListBuffer[Int]()
    def traversal(curNode: TreeNode): Unit = {
      if(curNode == null) return
      traversal(curNode.left)
      res.append(curNode.value)
      traversal(curNode.right)
    }
    traversal(root)
    res.toList
  }
}

后序遍历：（145. 二叉树的后序遍历）

object Solution {
  import scala.collection.mutable.ListBuffer
  def postorderTraversal(root: TreeNode): List[Int] = {
    val res = ListBuffer[Int]()
    def traversal(curNode: TreeNode): Unit = {
      if (curNode == null) return
      traversal(curNode.left)
      traversal(curNode.right)
      res.append(curNode.value)
    }
    traversal(root)
    res.toList
  }
}

Rust:

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        Self::traverse(&root, &mut res);
        res
    }

//前序遍历
    pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
        if let Some(node) = root {
            res.push(node.borrow().val);
            Self::traverse(&node.borrow().left, res);
            Self::traverse(&node.borrow().right, res);
        }
    }
//后序遍历
    pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
        if let Some(node) = root {
            Self::traverse(&node.borrow().left, res);
            Self::traverse(&node.borrow().right, res);
            res.push(node.borrow().val);
        }
    }
//中序遍历
    pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
        if let Some(node) = root {
            Self::traverse(&node.borrow().left, res);
            res.push(node.borrow().val);
            Self::traverse(&node.borrow().right, res);
        }
    }
}

C#

// 前序遍历
public IList<int> PreorderTraversal(TreeNode root)
{
    var res = new List<int>();
    if (root == null) return res;
    Traversal(root, res);
    return res;

}
public void Traversal(TreeNode cur, IList<int> res)
{
    if (cur == null) return;
    res.Add(cur.val);
    Traversal(cur.left, res);
    Traversal(cur.right, res);
}
// 中序遍历
public IList<int> InorderTraversal(TreeNode root)
{
    var res = new List<int>();
    if (root == null) return res;
    Traversal(root, res);
    return res;
}
public void Traversal(TreeNode cur, IList<int> res)
{
    if (cur == null) return;
    Traversal(cur.left, res);
    res.Add(cur.val);
    Traversal(cur.right, res);
}
// 后序遍历
public IList<int> PostorderTraversal(TreeNode root)
{
    var res = new List<int>();
    if (root == null) return res;
    Traversal(root, res);
    return res;
}
public void Traversal(TreeNode cur, IList<int> res)
{
    if (cur == null) return;
    Traversal(cur.left, res);
    Traversal(cur.right, res);
    res.Add(cur.val);
}

PHP

// 144.前序遍历
function preorderTraversal($root) {
    $output = [];
    $this->traversal($root, $output);
    return $output;
}

function traversal($root, array &$output) {
    if ($root->val === null) {
        return;
    }

    $output[] = $root->val;
    $this->traversal($root->left, $output);
    $this->traversal($root->right, $output);
}
// 94.中序遍历
function inorderTraversal($root) {
    $output = [];
    $this->traversal($root, $output);
    return $output;
}

function traversal($root, array &$output) {
    if ($root->val === null) {
        return;
    }

    $this->traversal($root->left, $output);
    $output[] = $root->val;
    $this->traversal($root->right, $output);
}
// 145.后序遍历
function postorderTraversal($root) {
    $output = [];
    $this->traversal($root, $output);
    return $output;
}

function traversal($root, array &$output) {
    if ($root->val === null) {
        return;
    }

    $this->traversal($root->left, $output);
    $this->traversal($root->right, $output);
    $output[] = $root->val;
}