欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 中级 - 中序遍历二叉树

程序员文章站 2022-05-19 21:05:40
...

中序遍历二叉树

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

示例:

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

输出: [1,3,2]

分析

只需要记住中序遍历的顺序:左->中->右

代码

只实现递归版本

迭代可以考虑使用栈存储遍历过的节点,“返回上一层”时,栈顶节点出栈

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        //中序的顺序:左->根->右
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> lists = new LinkedList<>();
            if(root == null){
                return lists;
            }
            else inOrder(lists,root);
            return lists;
        }
        private void inOrder(List<Integer> list,TreeNode root){
            if(root == null){
                return;
            }else{
                inOrder(list,root.left);
                list.add(root.val);
                inOrder(list,root.right);
            }
        }
    }