LeetCode之二叉树作题java

100. Same Tree

Total Accepted: 127501 Total Submissions: 294584 Difficulty: Easy

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int x) {

        val = x;

    }

}

 //递归调用，首先判断是否都是空，如果是，则返回true，否则若都不为空，则分两步
//走，如果根节点值相同，则看两者的左节点是否一样，再看右节点，若有不同，则返回false；
//还有就是其他情况：两树中有一树为空的情况，直接返回false

public class Solution {

    public boolean isSameTree(TreeNode root1, TreeNode root2){

        if(root1==null&&root2==null)

            return true;

        while(root1!=null&&root2!=null){

            if(root1.val==root2.val){

                return isSameTree(root1.left, root2.left)&&isSameTree(root1.right, root2.right);

            }else{

                return false;

            }

        }

        return false;

    }

}

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

minimum-depth-of-binary-tree

题目描述

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路：与求二叉树的深度类似，求二叉树的深度，主要是求二叉树的最长路径，此处求二叉树的最短路径，思路如下：

　　1.当root=null时，直接return 0；

　　2.当root.left=null且root.right=null时，直接return 1；

　　3.当root.left=null或者root.right=null时，递归调用（返回右子树最小长度）run(root.right)+1或(返回左子树最小长度)run(root.left)+1;

　　4.最后root.left!=null且root.right!=null时，返回左子树和右子树的最小路径长度；

public class Solution {

    public int run(TreeNode root) {

        if(root==null)

            return 0;

        if(root.left==null&&root.right==null)

            return 1;

        if(root.left==null)

            return run(root.right)+1;

        if(root.right==null)

            return run(root.left)+1;

        return Math.min(run(root.left),run(root.right))+1;

    }

}

binary-tree-postorder-traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree{1,#,2,3},

return[3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

考察二叉树的后序遍历：

非递归思路：使用栈来作为辅助

　　思路一：stack作为缓冲，保存左右孩子节点，stack1作为最终保存结果；

　　　　1.当root为空，直接返回空；

　　　　2.当root不为空时，当root入栈stack，直接出栈stack，如果该节点没有左右孩子，直接将该节点入栈stack1，最后出栈；

　　　　3.如果该节点有左右孩子，将其左右孩子依次入栈stack，保存访问过的节点，重复上面的过程，保证每次取栈顶的元素，左孩子在右孩子前面被访问，左孩子和右孩子都在根节点前面被访问。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

import java.util.*;

public class Solution {

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        if(root==null)

            return list;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        Stack<TreeNode> stack2 = new Stack<TreeNode>();

        stack.push(root);

        while(!stack.empty()){

            TreeNode curNode = stack.pop();

            if(curNode.left!=null){

                stack.push(curNode.left);

            }

            if(curNode.right!=null){

                stack.push(curNode.right);

            }

            stack2.push(curNode);

        }

        while(!stack2.empty()){

            list.add(stack2.pop().val);

        }

        return list;

    }

}

　　思路二：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

递归思路：

　　1.递归遍历左子树；

　　2.递归遍历右子树；

　　3.输出根节点；

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

import java.util.*;

public class Solution {

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        postorderTraversalHelper(root,list);

        return list;

    }

    public void postorderTraversalHelper(TreeNode root, ArrayList<Integer> list){

        if(root==null)

            return;

        postorderTraversalHelper(root.left,list);

        postorderTraversalHelper(root.right,list);

        list.add(root.val);

    }

}

binary-tree-preorder-traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree{1,#,2,3},

return[1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

import java.util.*;

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        preorderTraversalHelper(root, list);

        return list;

    }

    public void preorderTraversalHelper(TreeNode root, ArrayList<Integer> list){

        if(root==null)

            return;

        list.add(root.val);

        preorderTraversalHelper(root.left,list);

        preorderTraversalHelper(root.right,list);

    }

}

巴特西

LeetCode之二叉树作题java

100. Same Tree

101. Symmetric Tree

题目描述

最新文章

热门文章