luckydog

V1

2022/03/16阅读:42主题:默认主题

Code 94_102_104

二叉树的遍历

code_94
给定一个二叉树的根节点 root ,返回它的中序遍历。
来源:Leetcode 94题

树的数据结构

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode() {
        }
        
        TreeNode (int val) {
        this.val = val;
        }
        
        TreeNode (int val, TreeNode left, TreeNode right,) {
        this.val = val;
        this.left = left;
        this.right = right;
        }
}

中序遍历

  • 递归写法

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }

    public void inorder(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }

迭代(通过栈)

   public List<Integer> inorder(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Deque<TreeNode> stack = new LinkedList<>();
       while(root != null || !stack.isEmpty()) {
           while(root != null) {
               stack.push(root);
               root = root.left;
           }
           root = stack.pop();
           res.add(root.val);
           root = root.right;
       }
       return res;
   }

先序遍历(非递归)

先序遍历顺序为根-->左-->右,因此先访问根节点,而栈先进后出,如果先root再root.left再root.right进栈的话,它必然是root.right先于root.left出栈,因此要将root.right先入栈。

public List<Integer> inorder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(root.val);
            //先右节点进栈
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return res;
   }

后序遍历

有待完成

层序遍历 Leetcode 102

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            ans.add(list);
        }

层序遍历求深度 Leetcode 104

层序遍历一般求深度,宽度都可以

1.层序

public int maxDepth(TreeNode root) {
       int depth = 0;
       Deque<TreeNode> deque = new LinkedList<>();
       if (root == null) {
           return depth;
       }
       deque.offer(root);
       while (!deque.isEmpty()) {
           int size = deque.size();
           for (int i = 0; i < size; i++) {
               TreeNode node = deque.poll();
               if (node.left != null) {
                   deque.offer(node.left);
               }
               if (node.right != null) {
                   deque.offer(node.right);
               }
           }
           depth++;
       }
       return depth;
   }

2.递归

public int maxDepth(TreeNode root) {
       if (root == null) {
           return 0;
       }else {
           int leftMax = maxDepth(root.left);
           int rightMax = maxDepth(root.right);
           return Math.max(leftMax, rightMax) + 1;
       }
   }

分类:

后端

标签:

Java

作者介绍

luckydog
V1