模型与算法算法相关

画解算法:94. 二叉树的中序遍历

2019-07-31  本文已影响47人  DeppWang

题目链接

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

题目描述

给定一个二叉树,返回它的中序遍历。
示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
 
输出: [1,3,2]

解题方案

思路1:使用递归

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        traversal(root, list);
        return list;
    }

    private void traversal(TreeNode root, List<Integer> list) {
        if (root != null) {
            if (root.left != null) {
                traversal(root.left, list);
            }
            list.add(root.val);//如果当前节点没有左子树,记录其值
            if (root.right != null) {
                traversal(root.right, list);
            }
        }
    }
}

画解

0.png
1.png
2.png
3.png
3-2.png
4.png
5.png
5-2.png
6.png
6-2.png
7.png
8.png
9.png
9-2.png
10.png
10-2.png
image.png
11-2.png

思路2:使用栈

上一篇 下一篇

猜你喜欢

热点阅读