代码随想录-二叉树

************二叉树的前序遍历：

. - 力扣（LeetCode）

递归

public class LeetCode144 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new LinkedList<>();
        preOrder(root,res);
        return res;
    }

    private void preOrder(TreeNode root, List<Integer> res) {
        if (root==null){
            return;
        }
        res.add(root.val);
        preOrder(root.left,res);
        preOrder(root.right,res);
    }

}

迭代：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack=new LinkedList<>();
        List<Integer> res=new LinkedList<>();
        if (root==null){
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.right!=null) stack.push(pop.right);
            if (pop.left!=null) stack.push(pop.left);
        }
        return res;
    }
}

二叉树的后续遍历：

. - 力扣（LeetCode）

public class LeetCode145 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        postOrder(root,list);
        return list;
    }

    private void postOrder(TreeNode root, List<Integer> list) {
        if (root==null){
            return;
        }
        if (root.left!=null){
            postOrder(root.left,list);
        }
        if (root.right!=null){
            postOrder(root.right,list);
        }
        list.add(root.val);
    }

}

迭代：不太理解

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
       LinkedList<TreeNode> stack=new LinkedList<>();
        List<Integer> res=new LinkedList<>();
        if (root==null){
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.left!=null) stack.push(pop.left);
            if (pop.right!=null) stack.push(pop.right);
        }
        Collections.reverse(res);
        return res;
    }
}

二叉树的中序遍历

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new LinkedList<>();
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            if (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }else{
                cur = stack.pop();
                res.add(cur.val);
                cur=cur.right;
            }
        }
        return res;
    }
}

****二叉树的最小深度：
 

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        //只有当左右孩子都为null时才算
        if (root==null) return 0;
        if (root.left==null&&root.right==null) return 1;
        int min=Integer.MAX_VALUE;
        if (root.left!=null) min=Math.min(min,minDepth(root.left));
        if (root.right!=null) min=Math.min(min,minDepth(root.right));
        return 1+min;
    }
}

翻转二叉树：

. - 力扣（LeetCode）

递归：可以使用递归的大多都可以使用栈进行迭代

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 TreeNode invertTree(TreeNode root) {
        if (root==null) return root;
        if (root.left==null&&root.right==null) return root;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

迭代：

public TreeNode invertTree2(TreeNode root) {
        if (root==null) return root;
        if (root.left==null&&root.right==null) return root;
        LinkedList<TreeNode> stack=new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            TreeNode temp=pop.left;
            pop.left=pop.right;
            pop.right=temp;
            if (pop.left!=null) stack.push(pop.left);
            if (pop.right!=null) stack.push(pop.right);
        }
        return root;
    }