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

LeetCode 94. Binary Tree Inorder Traversal

程序员文章站 2022-05-20 13:50:01
...

问题描述

  • Given a binary tree, return the inorder traversal of its nodes’ values.
  • Follow up: Recursive solution is trivial, could you do it iteratively?
  • 地址

问题分析

  • 实现二叉树中序遍历的方法
    • 递归
    • 非递归
      • 教科书法(压左边界)
      • 金手指法

代码实现

  • 递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorderTraversal(root, res);
        return res;
    }

    public void inorderTraversal(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, res);
        res.add(root.val);
        inorderTraversal(root.right, res);
    }
  • 非递归:教科书法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); 
        TreeNode curNode = root;
        while (curNode != null || ! stack.isEmpty()) {
            while (curNode != null) {
                //第一次遇到该节点(前序)
                stack.push(curNode);
                curNode = curNode.left;
            }
            //第二次遇到该节点(中序)
            curNode = stack.pop();
            res.add(curNode.val);
            curNode = curNode.right;
        }
        return res;
    }
  • 非递归金手指法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<>();
        Stack<Command> stack = new Stack<>();
        //初始化
        stack.push(new Command(false, root));
        while(! stack.isEmpty()) {
            Command curCommand = stack.pop();
            TreeNode curRoot = curCommand.root;
            if (curCommand.isPrint) {
                res.add(curRoot.val);
            }else {
                //此时指令入栈顺序是右(遍历)根(打印)左(遍历)
                //出栈后便是左(遍历)根(打印)右(遍历),便实习了中序遍历
                if (curRoot.right != null) {
                    stack.push(new Command(false, curRoot.right));
                }
                stack.push(new Command(true, curRoot));
                if (curRoot.left != null) {
                    stack.push(new Command(false, curRoot.left));
                }
            }
        }
        return res;
    }

//用于指示该root是打印还是遍历
class Command{
    boolean isPrint;
    TreeNode root;
    public Command(boolean isPrint, TreeNode root) {
        this.isPrint = isPrint;
        this.root = root;
    }
}