leetcode练习

 1 /**
 2  * url:https://leetcode-cn.com/problems/implement-queue-using-stacks/
 3  * 解法思路：inStack和outStack两栈分别替代进队和出队，进队的时候进栈，出队时判断是出栈是否为空，将进栈全部放入出栈中，然后再出栈就是出队了，返回队列开头
 4  * 也一样需要把进栈放进出栈再返回栈顶
 5  */
 6 public class 用栈实现队列 {
 7     private Stack <Integer> inStack = new Stack <>();
 8     private Stack <Integer> outStack = new Stack <>();
 9     /** Initialize your data structure here. */
10     public 用栈实现队列() {
11 
12     }
13 
14     /** Push element x to the back of queue. */
15     public void push(int x) {
16         inStack.push(x);
17     }
18 
19     /** Removes the element from in front of queue and returns that element. */
20     public int pop() {
21         if(outStack.isEmpty()){
22             while (!inStack.isEmpty()){
23                 outStack.push(inStack.pop());
24             }
25         }
26         return outStack.pop();
27     }
28 
29     /** Get the front element. */
30     public int peek() {
31         if(outStack.isEmpty()){
32             while (!inStack.isEmpty()){
33                 outStack.push(inStack.pop());
34             }
35         }
36         return outStack.peek();
37     }
38 
39     /** Returns whether the queue is empty. */
40     public boolean empty() {
41         return  inStack.isEmpty() && outStack.isEmpty();
42     }
43 }

 1 /**
 2  * url：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
 3  * 解题思路：二叉树的某点高度等于该点左右子树中最大高度加1，所以采用递归的方式对左右子树的高度进行比较并加1，root节点为null时则为叶子节点，返回0.
 4  */
 5 public class 二叉树的深度 {
 6     public class TreeNode {
 7         int val;
 8         TreeNode left;
 9         TreeNode right;
10         TreeNode(int x) {
11             val = x;
12         }
13     }
14     public int maxDepth(TreeNode root) {
15         if (root == null) return 0;
16         return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
17     }
18 }

 1 /**
 2  * url：https://leetcode-cn.com/problems/invert-binary-tree/
 3  * 解题思路：二叉树的反转就是将左右子树交换，所以无论是前序遍历，中序遍历，后序遍历还是层级遍历都可将二叉树进行反转；
 4  *          当遍历到某个节点时将其左右子树交换，但需要注意的是中序遍历，因为root节点之前已经将左子树换成右子树。需要将后面要的right换成left
 5  */
 6 public class 翻转二叉树 {
 7     public class TreeNode {
 8         int val;
 9         TreeNode left;
10         TreeNode right;
11         TreeNode() {
12         }
13         TreeNode(int val) {
14             this.val = val;
15         }
16         TreeNode(int val, TreeNode left, TreeNode right) {
17             this.val = val;
18             this.left = left;
19             this.right = right;
20         }
21     }
22     //前序遍历
23     public TreeNode invertTree(TreeNode root) {
24         if(root==null) return root;
25         TreeNode tempTree = root.left;
26         root.left = root.right;
27         root.right = tempTree;
28         invertTree(root.left);
29         invertTree(root.right);
30         return root;
31     }
32     //后续遍历
33     public TreeNode invertTree(TreeNode root) {
34         if(root==null) return root;
35         invertTree(root.left);
36         invertTree(root.right);
37         TreeNode tempTree = root.left;
38         root.left = root.right;
39         root.right = tempTree;
40         return root;
41     }
42     //中序遍历
43     public TreeNode invertTree(TreeNode root) {
44         if(root==null) return root;
45         invertTree(root.left);
46         TreeNode tempTree = root.left;
47         root.left = root.right;
48         root.right = tempTree;
49         invertTree(root.left);
50         return root;
51     }
52 }